题解：P11262 [COTS 2018] 题日 Zapatak

不需要哈希的莫队做法！

注意到每次询问的两个区间长度是一样的，所以一次询问可以用两个区间的左端点和区间长度来描述。考虑莫队，维护一个桶 cnt，用来统计每个数在第一个区间中的出现次数减去在第二个区间中的出现次数。询问的区间相似（即答案为是）当且仅当 cnt 中只有一个 1、一个 -1，其他全为 0。只需再维护桶中 1 的个数和 0 的个数即可。

时间复杂度分析类似带修莫队，块长取 n^{2/3} 时达到最优时间复杂度 O(n^{5/3})。实测块长取 2500 时可以通过，但是时间还是卡得很紧，喜提最劣解。

#include<bits/stdc++.h>
using I=int;
template<class T,I N>using A=std::array<T,N>;
I read(){
  int c;while(!isdigit(c=getchar()));
  I x=c-'0';while(isdigit(c=getchar()))x=x*10+c-'0';
  return x;
}
int main(){
  const I N=1e5,M=1e5;
  I n,m;std::cin>>n>>m;
  static I a[N],b[N];for(I i=0;i<n;i++)b[i]=a[i]=read();
  std::sort(b,b+n);I bz=std::unique(b,b+n)-b;
  for(I i=0;i<n;i++)a[i]=std::lower_bound(b,b+bz,a[i])-b;
  static A<I,4>qr[M];
  for(I i=0;i<m;i++){
    I l1=read()-1,r1=read(),l2=read()-1,r2=read();
    qr[i]={l1,l2,r1-l1,i};
  }
  I blk=2500;
  std::sort(qr,qr+m,[&](auto&&x,auto&&y){
    return x[0]/blk!=y[0]/blk?x[0]<y[0]:x[1]/blk!=y[1]/blk?x[1]<y[1]:x[2]<y[2];
  });
  I l1=0,l2=0,k=0,w0=bz,w1=0;
  static I cnt[M];
  auto add=[&](I x){I&c=cnt[a[x]];w0+=(c==-1)-(c==0);w1+=(c==0)-(c==1);c++;};
  auto del=[&](I x){I&c=cnt[a[x]];w0+=(c==1)-(c==0);w1+=(c==2)-(c==1);c--;};
  static I ww[M];
  for(I i=0;i<m;i++){
    auto[ql1,ql2,qk,qi]=qr[i];
    for(;k>qk;k--)del(l1+k-1),add(l2+k-1);
    for(;l1<ql1;l1++)add(l1+k),del(l1);
    for(;l1>ql1;l1--)add(l1-1),del(l1+k-1);
    for(;l2<ql2;l2++)del(l2+k),add(l2);
    for(;l2>ql2;l2--)del(l2-1),add(l2+k-1);
    for(;k<qk;k++)add(l1+k),del(l2+k);
    ww[qi]=w1==1&&w0==bz-2;
  }
  for(I i=0;i<m;i++)puts(ww[i]?"DA":"NE");
  return 0;
}