19_03_28校内训练[相似字符串]

题意

给出一个长度为n的序列，有m次询问，每次询问[l₁,r₁]，[l₂,r₂]的区间，问排序后相同位置的不同数字个数是否小于等于1。如[1,3,2,2],[1,3,2,3]排序后为[1,2,2,3]和[1,2,3,3]，不同的有2个，不符合。n,m≤1,000,000，数的大小≤50,000。

思考

有排序，权值还小，自然想到可持久化线段树。

不同数小于等于1，自然先想完全相同的条件。

先以权值为下表，按加入数组的顺序加入可持久化线段树，这样得到了1~n不同大小的数的前缀和。

若是完全相同，先做一次r-(l-1)，由于排序后的数，相同的没有位置关系，哈希即可。

有一个不同？则必然存在最左边和最右边的端点，使得该位置上出现的数的个数不同。不同的数超过2个，及不符合（实际上是1，但会算两边）。否则再查询这个开区间中，是否还有其余数。若有，显然不满足。否则满足。

线段树上二分即可。O(nlogn+mlogn)。

记得不要用hash这个变量名就能过了。

代码

  1 #include<bits/stdc++.h>
  2 using namespace std;
  3 typedef long long int ll;
  4 const ll h1=13131;
  5 const ll h2=23333;
  6 const ll h3=15787;
  7 const ll mod1=1000000007;
  8 const ll mod2=998244353;
  9 const ll mod3=19260817;
 10 const ll maxn=1E5+5;
 11 ll q1[maxn],q2[maxn],q3[maxn],maxx=100000;
 12 int read()
 13 {
 14     char ch=getchar();
 15     while(ch<'0'||'9'<ch)ch=getchar();
 16     int sum=ch-'0';
 17     ch=getchar();
 18     while('0'<=ch&&ch<='9')
 19     {
 20         sum=sum*10+ch-'0';
 21         ch=getchar();
 22     }
 23     return sum;
 24 }
 25 struct Hash
 26 {
 27     ll a1,a2,a3;
 28     int sum;
 29     Hash(ll x=0,ll y=0,ll z=0,ll s=0){a1=(x+mod1)%mod1,a2=(y+mod2)%mod2,a3=(z+mod3)%mod3,sum=s;}
 30     void operator=(Hash x){a1=x.a1,a2=x.a2,a3=x.a3,sum=x.sum;}
 31     Hash operator+(Hash x){return Hash(a1+x.a1,a2+x.a2,a3+x.a3,sum+x.sum);}
 32     Hash operator-(Hash x){return Hash(a1-x.a1,a2-x.a2,a3-x.a3,sum-x.sum);}
 33     bool operator==(Hash x){return a1==x.a1&&a2==x.a2&&a3==x.a3;}
 34 }t[maxn*20],g[maxn];
 35 int ls[maxn*20],rs[maxn*20],T,n,m,cur,a[maxn],root[maxn];
 36 void init()
 37 {
 38     q1[0]=q2[0]=q3[0]=1;
 39     for(int i=1;i<=100000;++i)
 40     {
 41         q1[i]=q1[i-1]*h1%mod1;
 42         q2[i]=q2[i-1]*h2%mod2;
 43         q3[i]=q3[i-1]*h3%mod3;
 44         g[i]=Hash(q1[i],q2[i],q3[i],1);
 45     }
 46 }
 47 void insert(int l,int r,int pos,int&num,int pre)
 48 {
 49     num=++cur;
 50     t[num]=t[pre];
 51     ls[num]=ls[pre];
 52     rs[num]=rs[pre];
 53     t[num]=t[num]+g[pos];
 54     if(l==r)return;
 55     int mid=(l+r)>>1;
 56     if(pos<=mid)insert(l,mid,pos,ls[num],ls[pre]);
 57     else insert(mid+1,r,pos,rs[num],rs[pre]);
 58 }
 59 int GGAx,GGAy,GGAz,GGBx,GGBy,GGBz;
 60 void findL(int l,int r,int l1,int r1,int l2,int r2)
 61 {
 62     if(l==r)
 63     {
 64         GGAx=l;
 65         GGAy=t[r1].sum-t[l1].sum;
 66         GGAz=t[r2].sum-t[l2].sum;
 67         return;
 68     }
 69     int mid=(l+r)>>1;
 70     Hash L1=t[ls[r1]]-t[ls[l1]],R1=t[rs[r1]]-t[rs[l1]];
 71     Hash L2=t[ls[r2]]-t[ls[l2]],R2=t[rs[r2]]-t[rs[l2]];
 72     if(!(L1==L2))
 73     {
 74         l1=ls[l1],r1=ls[r1];
 75         l2=ls[l2];r2=ls[r2];
 76         findL(l,mid,l1,r1,l2,r2);
 77     }
 78     else
 79     {
 80         l1=rs[l1],r1=rs[r1];
 81         l2=rs[l2],r2=rs[r2];
 82         findL(mid+1,r,l1,r1,l2,r2);
 83     }
 84 }
 85 void findR(int l,int r,int l1,int r1,int l2,int r2)
 86 {
 87     if(l==r)
 88     {
 89         GGBx=l;
 90         GGBy=t[r1].sum-t[l1].sum;
 91         GGBz=t[r2].sum-t[l2].sum;
 92         return;
 93     }
 94     int mid=(l+r)>>1;
 95     Hash L1=t[ls[r1]]-t[ls[l1]],R1=t[rs[r1]]-t[rs[l1]];
 96     Hash L2=t[ls[r2]]-t[ls[l2]],R2=t[rs[r2]]-t[rs[l2]];
 97     if(!(R1==R2))
 98     {
 99         l1=rs[l1],r1=rs[r1];
100         l2=rs[l2],r2=rs[r2];
101         findR(mid+1,r,l1,r1,l2,r2);
102     }
103     else
104     {
105         l1=ls[l1],r1=ls[r1];
106         l2=ls[l2];r2=ls[r2];
107         findR(l,mid,l1,r1,l2,r2);
108     }
109 }
110 int askSeq(int L,int R,int l,int r,int num)
111 {
112     if(L>R)return 0;
113     if(L<=l&&r<=R)return t[num].sum;
114     else if(r<L||R<l)return 0;
115     int mid=(l+r)>>1;
116     return askSeq(L,R,l,mid,ls[num])+askSeq(L,R,mid+1,r,rs[num]);
117 }
118 void YES(){putchar('Y');putchar('E');putchar('S');putchar('\n');}
119 void NO(){putchar('N');putchar('O');putchar('\n');}
120 void solve()
121 {
122     n=read();m=read();
123     for(int i=1;i<=n;++i)
124     {
125         a[i]=read();
126         insert(1,maxx,a[i],root[i],root[i-1]);
127     }
128     while(m--)
129     {
130         int l1,r1,l2,r2;
131         l1=read();r1=read();l2=read();r2=read();
132         if(l1>r1)swap(l1,r1);
133         if(l2>r2)swap(l2,r2);
134         if(t[root[r1]]-t[root[l1-1]]==t[root[r2]]-t[root[l2-1]])YES();
135         else
136         {
137             findL(1,maxx,root[l1-1],root[r1],root[l2-1],root[r2]);
138             findR(1,maxx,root[l1-1],root[r1],root[l2-1],root[r2]);
139             int x=GGAx;
140             int y=GGBx;
141             int d1=askSeq(x+1,y-1,1,maxx,root[r1])-askSeq(x+1,y-1,1,maxx,root[l1-1]);
142             int d2=askSeq(x+1,y-1,1,maxx,root[r2])-askSeq(x+1,y-1,1,maxx,root[l2-1]);
143             if(abs(GGAy-GGAz)+abs(GGBy-GGBz)>2||d1!=0||d2!=0)NO();
144             else YES();
145         }
146     }
147 }
148 void clear()
149 {
150     for(int i=0;i<=cur;++i)t[i].a1=t[i].a2=t[i].a3=ls[i]=rs[i]=0;
151     for(int i=0;i<=n;++i)root[i]=0;
152     cur=0;
153 }
154 int main()
155 {
156 //    freopen("sequence.in","r",stdin);
157 //    freopen("sequence.out","w",stdout);
158     ios::sync_with_stdio(false);
159     init();
160     T=read();
161     while(T--)
162     {
163         solve();
164         if(T!=0)clear();
165     }
166     return 0;
167 }

View Code