P1972 HH的项链 离线+树状数组
这题好像用线段树做有点……超出我的智商了
如果数字范围小于60的话还可以用状压
但是吧1e6有点过分了0.0
今天刚学树状数组，随便写了个线段树经典修改题，就来补这道题了
嘤嘤嘤菜鸡互啄
题意
给出m个询问L,R ，问[L,R]内共有多少个不同的数字
思路
假设给出一个数列1445，如何用离线处理呢？求区间[1,4],现在先假设每个数字的值都是1，那么这样前缀和加起来显然是4，但是显然不是，因为第三个数4和第二个数4是重复的，那么就可以把第二个数4设为-1，第三个数4设为1，这样前缀和就是3，就是正确的
也就是说，如果这个数字已经出现过，就把上一次它出现位置的数字改成-1
这样就可以保证前缀和维护区间不同数字的数量是可行的！！！
注意：如果此时再要求区间[2,2]的不同的数字的话岂不是-1吗？因此我们还需要一个排序操作，把区间的右端点按递增排序，这样就可以保证在不断修改值的过程中是不影响后续答案的
如果这题再加一个修改操作的话可能。。。会有点复杂了，不知道树状数组能不能做
/** * Author1: low-equipped w_udixixi * Author2: Sher丶lock * Date :2019-09-01 **/#include<cstdio>#include<cstring>#include<algorithm>#include<iostream>#include<string>#include<vector>#include<stack>#include<bitset>#include<cstdlib>#include<cmath>#include<set>#include<list>#include<deque>#include<queue>#include<map>#definell long long#definepb push_back#definerep(x,a,b) for (int x=a;x<=b;x++)#definerepp(x,a,b) for (int x=a;x<b;x++)#defineW(x) printf("%d\n",x)#defineWW(x) printf("%lld\n",x)#definepi 3.14159265358979323846#definemem(a,x) memset(a,x,sizeof a)#definelson rt<<1,l,mid#definerson rt<<1|1,mid+1,rusing namespace std;constintmaxn=2e6+7;constintINF=1e9;constll INFF=1e18;inta[maxn];inttree[maxn];intlast[maxn];//用来记录该数字上一次出现的位置intans[maxn];intn,m;structnode{intl,r,id;}p[maxn];boolcmp1(node a,node b){returna.r<b.r;}intf(intx){returnx&(-x);}***********************intgetsum(intx){intsum=0;for(inti=x;i>0;i-=f(i)){sum+=tree[i];}returnsum;}voidadd(intx,inty){for(inti=x;i<=n;i+=f(i)){tree[i]+=y;}}***********************************树状数组核心语句intmain(){scanf("%d",&n);rep(i,1,n){scanf("%d",&a[i]);}scanf("%d",&m);rep(i,1,m){scanf("%d%d",&p[i].l,&p[i].r);p[i].id=i;}sort(p+1,p+1+m,cmp1);intk=1;rep(i,1,n){if(last[a[i]])add(last[a[i]],-1);add(i,1);last[a[i]]=i;while(p[k].r==i)//不能用if{ans[p[k].id]=getsum(p[k].r)-getsum(p[k].l-1);k++;}}rep(i,1,m)W(ans[i]);return0;}
