Uva 3767 Dynamic len(set(a[L:R])) 树套树

Dynamic len(set(a[L:R]))

Time Limit: 20 Sec

Memory Limit: 256 MB

题目连接

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=3767

Description

给你n个数，m次操作

Q x y 询问[x+1,y]有多少个不同的数

M x y 将第x+1个数修改成y

Input

n，50000 询问50000次，修改的y的数最大1e6

Output

Sample Input

7 4
1 2 1 3 2 1 4
Q 1 6
M 3 2
Q 1 6
Q 3 5

Sample Output

3
2
1

HINT

题意

题解：

树套树

首先我们对于每个元素，将这个数的值修改成 这个数前面离最近的数，在哪儿

比如样例 1 2 1 3 2 1 4

我们可以看出 0 0 1 0 2 3 0

然后我们每次的询问操作就是查询区间有多少个数小于l，这个就是平衡树或者主席树来解决就好了（划分树已经成为了时代的眼泪

修改的话，就得树套树，然后我们再用set维护一下这个数后面的数是什么，前面的数是什么就好了

注意，修改会修改3个数哦~

代码：

#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<map>
#include<cstring>
#include<set>
#include<ctime>
using namespace std;
inline long long read()
{long long x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;
}
#define maxn 1500005
int tmp=0;
int a[maxn];
int c[maxn];
int b[maxn];
int n,m;
set<int> H[maxn];
////treap
struct Treap
{int root[maxn],sz,s[maxn],ls[maxn],rs[maxn],v[maxn],w[maxn],rnd[maxn];void init(){memset(root,0,sizeof(root));sz=0;}void Updata(int k){s[k]=s[ls[k]]+s[rs[k]]+w[k];}void Rturn(int &k){int t;t=ls[k],ls[k]=rs[t],rs[t]=k,s[t]=s[k];Updata(k);k=t;}void Lturn(int &k){int t;t=rs[k],rs[k]=ls[t],ls[t]=k,s[t]=s[k];Updata(k);k=t;}void Insert(int &k,int num){if(!k){k=++sz;s[k]=w[k]=1;ls[k]=rs[k]=0;rnd[k]=rand();v[k]=num;return;}s[k]++;if(v[k]==num)w[k]++;else if(num<v[k]){Insert(ls[k],num);if(rnd[ls[k]]<rnd[k])Rturn(k);}else{Insert(rs[k],num);if(rnd[rs[k]]<rnd[k])Lturn(k);}}void Del(int &k,int num){if(v[k]==num){if(w[k]>1){w[k]--;s[k]--;return;}if(ls[k]*rs[k]==0)k=ls[k]+rs[k];else if(rnd[ls[k]]<rnd[rs[k]])Rturn(k),Del(k,num);elseLturn(k),Del(k,num);}else if(num<v[k]){Del(ls[k],num);s[k]--;}else{Del(rs[k],num);s[k]--;}}void Find(int k,int num){if(!k)return;if(v[k]<=num){tmp+=s[ls[k]]+w[k];Find(rs[k],num);}else Find(ls[k],num);}
}Tr;//线段树
int lowbit(int x)
{return x&(-x);
}
void Bit_updata(int x,int v)
{if(x==0)return;for(;x<=n;x+=lowbit(x))Tr.Insert(Tr.root[x],v);
}
void Bit_change(int x,int v)
{if(x==0)return;for(;x<=n;x+=lowbit(x))Tr.Del(Tr.root[x],v);
}
void Bit_query(int x,int num)
{if(x<=0)return;for(;x;x-=lowbit(x))Tr.Find(Tr.root[x],num);
}
///

void change(int x,int y)
{Bit_change(x,a[x]);H[b[x]].erase(x);int T = *H[b[x]].upper_bound(x);if(T!=n+5){Bit_change(T,x);Bit_updata(T,a[x]);a[T]=a[x];}b[x]=y;T = *--H[b[x]].upper_bound(x);a[x]=T;int MM = T;Bit_updata(x,a[x]);H[y].insert(x);T = *H[b[x]].upper_bound(x);if(T!=n+5){Bit_change(T,MM);Bit_updata(T,x);a[T]=x;}
}
int main()
{scanf("%d%d",&n,&m);for(int i=0;i<1000005;i++)H[i].insert(0),H[i].insert(n+5);for(int i=1;i<=n;i++){scanf("%d",&b[i]);H[b[i]].insert(i);}for(int i=1;i<=n;i++){a[i]=c[b[i]];c[b[i]]=i;Bit_updata(i,a[i]);}char op[5];int x,y;for(int i=1;i<=m;i++){scanf("%s%d%d",op,&x,&y);x++;if(op[0]=='Q'){int Ans1,Ans2;tmp = 0,Bit_query(y,x-1),Ans1=tmp;tmp = 0,Bit_query(x-1,x-1),Ans2=tmp;printf("%d\n",Ans1-Ans2);}elsechange(x,y);}
}