入门级数据结构算法。复习一下，分别手写一个。
线段树版本（过了CF上的https://codeforces.com/contest/1291/problem/D）：
1 #include<bits/stdc++.h> 2 #define f(i,a,b) for(int i=a;i<=b;i++) 3 using namespace std; 4 struct qujian{ 5 int l,r,index; 6 friend bool operator < (const qujian q1,const qujian q2){ 7 return q1.r<q2.r; 8 } 9 }qu[100005]; 10 int q; 11 12 const int N=2e5+5; 13 int a[N]; 14 struct node{ 15 int l,r,val; 16 }tree[N<<2]; 17 void build(int rt,int l,int r){ 18 tree[rt].l=l,tree[rt].r=r; 19 if(l==r){ 20 tree[rt].val=0; 21 return; 22 } 23 int mid=l+r>>1; 24 build(rt<<1,l,mid); 25 build(rt<<1|1,mid+1,r); 26 tree[rt].val=tree[rt<<1].val+tree[rt<<1|1].val; 27 } 28 void update(int rt,int pos,int val){ 29 if(tree[rt].l==tree[rt].r&&pos==tree[rt].l){ 30 tree[rt].val+=val; 31 return; 32 } 33 int mid=tree[rt].l+tree[rt].r>>1; 34 if(pos<=mid) update(rt<<1,pos,val); 35 else update(rt<<1|1,pos,val); 36 tree[rt].val+=val; 37 } 38 int query(int rt,int l,int r){ 39 if(l<=tree[rt].l&&r>=tree[rt].r) return tree[rt].val; 40 int mid=tree[rt].l+tree[rt].r>>1; 41 if(l>mid) return query(rt<<1|1,l,r); 42 else if(r<=mid) return query(rt<<1,l,r); 43 else return query(rt<<1,l,mid)+query(rt<<1|1,mid+1,r); 44 } 45 46 map<char,int> mp; 47 char b[N]; 48 int ans[N]; 49 50 bool cmp(const qujian q1,const qujian q2){ 51 return q1.index<q2.index; 52 } 53 54 int main(){ 55 scanf("%s",b+1); 56 int len=strlen(b+1); 57 scanf("%d",&q); 58 f(i,1,q) scanf("%d%d",&qu[i].l,&qu[i].r),qu[i].index=i; 59 sort(qu+1,qu+1+q); 60 //f(i,1,q) cout<<qu[i].l<<" "<<qu[i].r<<endl; 61 int cur=1; 62 build(1,1,len); 63 f(i,1,q){ 64 f(j,cur,qu[i].r){ 65 //cout<<"the current qujian is "<<qu[i].l<<" "<<qu[i].r<<endl; 66 int p=mp[b[j]]; 67 if(p!=0){ 68 update(1,p,-1); 69 //cout<<b[j]<<" has appeared at "<<p<<endl; 70 } 71 update(1,j,1); 72 //cout<<b[j]<<" last appeared at "<<j<<endl; 73 //cout<<"now the "<<j<<" is "<<query(1,j,j)<<endl; 74 mp[b[j]]=j; 75 } 76 cur=qu[i].r+1; 77 ans[qu[i].index]=query(1,qu[i].l,qu[i].r); 78 //cout<<qu[i].index<<":["<<qu[i].l<<","<<qu[i].r<<"]="<<query(1,qu[i].l,qu[i].r)<<endl; 79 } 80 //f(i,1,q) cout<<ans[i]<<" "; 81 sort(qu+1,qu+1+q,cmp); 82 f(i,1,q){ 83 if(qu[i].r-qu[i].l+1==1){ 84 puts("YES"); 85 } 86 else if(ans[i]>=3){ 87 puts("YES"); 88 } 89 else if(b[qu[i].l]!=b[qu[i].r]){ 90 puts("YES"); 91 } 92 else puts("NO"); 93 } 94 }
树状数组版本（怪不得潘神这么喜欢，写起来确实短得多）：
1 #include<bits/stdc++.h> 2 #define f(i,a,b) for(int i=a;i<=b;i++) 3 using namespace std; 4 struct qujian{ 5 int l,r,index; 6 friend bool operator < (const qujian q1,const qujian q2){ 7 return q1.r<q2.r; 8 } 9 }qu[100005]; 10 bool cmp(const qujian q1,const qujian q2){ 11 return q1.index<q2.index; 12 } 13 const int N=1e5+5; 14 map<int,int> mp; 15 int ans[N]; 16 int len[N]; 17 int n,q; 18 int a[N]; 19 int tree[N]; 20 #define lowbit(x) (x&(-x)) 21 void update(int pos,int val){ 22 while(pos<=n){ 23 tree[pos]+=val; 24 pos+=lowbit(pos); 25 } 26 } 27 int sum_1_to_pos(int pos){ 28 int ans=0; 29 while(pos>0){ 30 ans+=tree[pos]; 31 pos-=lowbit(pos); 32 } 33 return ans; 34 } 35 #define query(x,y) (sum_1_to_pos(y)-sum_1_to_pos(x-1)) 36 37 int main(){ 38 scanf("%d%d",&n,&q); 39 f(i,1,n) scanf("%d",&a[i]); 40 f(i,1,q) scanf("%d%d",&qu[i].l,&qu[i].r),qu[i].index=i,len[i]=qu[i].r-qu[i].l+1; 41 sort(qu+1,qu+1+q); 42 int cur=1; 43 f(i,1,q){ 44 f(j,cur,qu[i].r){ 45 int p=mp[a[j]]; 46 if(p!=0){ 47 update(p,-1); 48 } 49 update(j,1); 50 mp[a[j]]=j; 51 } 52 cur=qu[i].r+1; 53 ans[qu[i].index]=query(qu[i].l,qu[i].r); 54 } 55 f(i,1,q){ 56 if(ans[i]==len[i]) puts("Yes"); 57 else puts("No"); 58 } 59 }