因为他的相似是在排完序下的

那我就在排序的情况下hash啊

这怎么hash啊

主席树啊！

没了

1 #include 
     
        2 #define MAXNODE 5000000  3 #define MAX 200000  4 using namespace std;  5 int NODE,T,n,q,_l,_r,L,R;  6 int a[MAX],val[MAX],ma[MAX],root[MAX];  7 int tr[MAXNODE],c[MAXNODE][2];  8 int change(int acc,int l,int r,int x,int y)  9 { 10     if(l==r) 11     { 12         tr[++NODE]=y+tr[acc]; 13         c[NODE][0]=c[NODE][1]=0; 14         return NODE; 15     } 16     int now=++NODE,mid=l+r>>1; 17     if(x<=mid) 18         c[now][0]=change(c[acc][0],l,mid,x,y), 19         c[now][1]=c[acc][1]; 20     else 21         c[now][0]=c[acc][0], 22         c[now][1]=change(c[acc][1],mid+1,r,x,y); 23     tr[now]=tr[c[now][0]]+tr[c[now][1]]; 24     return now; 25 } 26 int tre(int rt,int x) 27 { 28     int ret=0; 29     for(int now=root[rt],l=1,r=MAX;l
      
       >1; 32         if(x<=mid) 33         { 34             r=mid,now=c[now][0]; 35             if(r==x) return ret+tr[now]; 36         } 37         if(x>mid) 38             l=mid+1,ret+=tr[c[now][0]],now=c[now][1]; 39     } 40     return ret; 41 } 42 int ha(int l,int r,int L,int R) 43 { 44     return tre(r,R)-tre(r,L-1)-tre(l-1,R)+tre(l-1,L-1); 45 } 46 int main() 47 { 48     srand(time(0)); 49     for(scanf("%d",&T);T;T--) 50     { 51         scanf("%d%d",&n,&q); 52         for(int i=1;i<=n;i++) 53         { 54             scanf("%d",&a[i]); 55             val[i]=ma[a[i]]?ma[a[i]]:(ma[a[i]]=rand()); 56     //        val[i]=a[i]; 57         } 58         root[0]=1;c[1][0]=c[1][1]=0;tr[1]=0;NODE=1; 59         for(int i=1;i<=n;i++) 60             root[i]=change(root[i-1],1,MAX,a[i],val[i]); 61         for(int i=1;i<=q;i++) 62         { 63             scanf("%d%d%d%d",&_l,&_r,&L,&R); 64             bool gg=0; 65             for(int l=1,r=MAX;l
       
        >1; 68                 if(ha(_l,_r,l,mid)==ha(L,R,l,mid)) 69                     l=mid+1; 70                 else 71                 if(ha(_l,_r,mid+1,r)==ha(L,R,mid+1,r)) 72                     r=mid; 73                 else 74                 { 75                     int ll=l,rr=mid; 76                     for(;ll
        
         >1; 79                         if(ha(_l,_r,ll,mm)==ha(L,R,ll,mm)) ll=mm+1; 80                         else rr=mm; 81                     } 82                     int tt=ll; 83                     ll=mid+1,rr=r; 84                     for(;ll
         
          >1; 87                         if(ha(_l,_r,mm+1,rr)==ha(L,R,mm+1,rr)) rr=mm; 88                         else ll=mm+1; 89                     } 90                     int ttt=ll; 91                     if(tt==ttt-1 || ha(_l,_r,tt+1,ttt-1)==0 && ha(L,R,tt+1,ttt-1)==0) break; 92                     else 93                     { 94                         gg=1; 95                         break; 96                     } 97                 } 98             } 99             puts((gg==1)?"NO":"YES");100         }101     }102     return 0;103 }