贪婪大陆

题面描述

人类被蚂蚁们逼到了 Greed Island 上的一个海湾。现在，小 FF 的后方是一望无际的大海， 前方是变异了的超 级蚂蚁。 小 FF 还有大好前程，他可不想命丧于此， 于是他派遣手下最后一批改造 SCV 布置地雷以阻挡蚂蚁们的进攻。

小 FF 最后一道防线是一条长度为 N 的战壕， 小 FF 拥有无数多种地雷，而 SCV 每次 可以在[ L , R ]区间埋放同一种不同于之前已经埋放的地雷。 由于情况已经十万火急，小 FF 在某些时候可能会询问你在[ L’ , R’] 区间内有多少种不同的地雷， 他希望你能尽快的给 予答复。

输入格式

第一行为两个整数 n 和 m； n 表示防线长度， m 表示 SCV 布雷次数及小 FF 询问 的次数总和。

接下来有 m 行， 每行三个整数 Q，L , R； 若 Q=1 则表示 SCV 在[ L , R ]这段区间 布上一种地雷， 若 Q=2 则表示小 FF 询问当前[ L , R ]区间总共有多少种地雷。

输出格式

对于小 FF 的每次询问，输出一个答案（单独一行），表示当前区间地雷总数。

样例

此题仔细看题可以发现，题目是让我们求得地雷的种数，而不是地雷的个数，所以我们可以单点修改就好，不需要进行区间修改，只要把x和y的值分别++，在回溯时可以直接加上去，在查询时，直接查询值就好了，我们可以有一个思路，如果直接搞x，y区间的话不是很好搞，我们可以把x，y上的点分别++，就可以了，在统计的时候直接统计1……x-1，和1……y，然后1……y减去1……x-1就得出来想……y的种数了，思路轻巧，以后还是要仔细理解

代码

#include<bits/stdc++.h>
using namespace std;
const int oi=1000010;
struct hf1
{
	int l1;
	int r1;
	int dat1;
}t1[oi*4];
struct hf2
{
	int l2;
	int r2;
	int dat2;
}t2[oi*4];
void build1(int p,int l,int r)
{
	t1[p].l1=l;
	t1[p].r1=r;
	if(l==r)
	{
		return;
	}
	int mid=(l+r)/2;
	build1(p*2,l,mid);
	build1(p*2+1,mid+1,r);
	t1[p].dat1=t1[p*2].dat1+t1[p*2+1].dat1;
}
void change1(int p,int x)
{
	if(t1[p].l1==t1[p].r1)
	{
		t1[p].dat1++;
		return;
	} 
	int mid=(t1[p].l1+t1[p].r1)/2;
	if(x<=mid)
	change1(p*2,x);
	else
	change1(p*2+1,x);
	t1[p].dat1=t1[p*2].dat1+t1[p*2+1].dat1;
}
int ask1(int p,int l,int r)
{
	if(l<=t1[p].l1&&t1[p].r1<=r)
	{
		return t1[p].dat1;
	}
	int mid=(t1[p].l1+t1[p].r1)/2;
	int v=0;
	if(l<=mid)
	v+=ask1(p*2,l,r);
	if(r>mid)
	v+=ask1(p*2+1,l,r);
	t1[p].dat1=t1[p*2].dat1+t1[p*2+1].dat1;
	return v;
}
void build2(int p,int l,int r)
{
	t2[p].l2=l;
	t2[p].r2=r;
	if(l==r)
	{
		return;
	}
	int mid=(l+r)/2;
	build2(p*2,l,mid);
	build2(p*2+1,mid+1,r);
	t2[p].dat2=t2[p*2].dat2+t2[p*2+1].dat2;
}
void change2(int p,int x)
{
	if(t2[p].l2==t2[p].r2)
	{
		t2[p].dat2++;
		return;
	} 
	int mid=(t2[p].l2+t2[p].r2)/2;
	if(x<=mid)
	change2(p*2,x);
	else
	change2(p*2+1,x);
	t2[p].dat2=t2[p*2].dat2+t2[p*2+1].dat2;
}
int ask2(int p,int l,int r)
{
	if(l<=t2[p].l2&&t2[p].r2<=r)
	{
		return t2[p].dat2;
	}
	int mid=(t2[p].l2+t2[p].r2)/2;
	int v=0;
	if(l<=mid)
	v+=ask2(p*2,l,r);
	if(r>mid)
	v+=ask2(p*2+1,l,r);
	t2[p].dat2=t2[p*2].dat2+t2[p*2+1].dat2;
	return v;
}
int main()
{
	freopen("greedisland.in","r",stdin);
	freopen("greedisland.out","w",stdout);
	int n,m;
	cin>>n>>m;
	build1(1,1,n);
	build2(1,1,n);
	int sum=0;
	for(int i=1;i<=m;i++)
	{
		int q,x,y;
		cin>>q>>x>>y;
		if(q==1)
		{
			change1(1,x);
			change2(1,y); 
			sum++;
		}
		if(q==2)
		{
			cout<<ask1(1,1,y)-ask2(1,1,x-1)<<endl;
		}
	}
}