P1972 HH的项链 离线+树状数组

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 **/#includecstdio#includecstring#includealgorithm#includeiostream#includestring#includevector#includestack#includebitset#includecstdlib#includecmath#includeset#includelist#includedeque#includequeue#includemap#definell long long#definepb push_back#definerep(x,a,b) for (int xa;xb;x)#definerepp(x,a,b) for (int xa;xb;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 rt1,l,mid#definerson rt1|1,mid1,rusing namespace std;constintmaxn2e67;constintINF1e9;constll INFF1e18;inta[maxn];inttree[maxn];intlast[maxn];//用来记录该数字上一次出现的位置intans[maxn];intn,m;structnode{intl,r,id;}p[maxn];boolcmp1(node a,node b){returna.rb.r;}intf(intx){returnx(-x);}***********************intgetsum(intx){intsum0;for(intix;i0;i-f(i)){sumtree[i];}returnsum;}voidadd(intx,inty){for(intix;in;if(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].idi;}sort(p1,p1m,cmp1);intk1;rep(i,1,n){if(last[a[i]])add(last[a[i]],-1);add(i,1);last[a[i]]i;while(p[k].ri)//不能用if{ans[p[k].id]getsum(p[k].r)-getsum(p[k].l-1);k;}}rep(i,1,m)W(ans[i]);return0;}