bzoj 3809 Gtyの二強制妹シーケンス

テーマ
n個の要素の配列、元素サイズ∈[1,n]は、[l,r]に問い合わせるたびに、数値[s,t]にどれぐらいのn<=1 e 5,m<=1 e 6]が現れますか?
問題を解く
発見しやすいのは、チームを作って樹状の配列で維持するという複雑さです.O(n\m l o g n)O(n\sqrt m logn)O(nm logn)です.Tにするべきです.実は専用に送ってみました.確かにTです.nとmの違いに注目して、必要な操作を分析します.二回前に私達が木の形の配列でメンテナンスすると、これらは全部lognです.私達は2の複雑さを犠牲にして1の複雑度を下げることを考えています.ブロックを分けて、私達は分塊で値を維持します.すると、挿入はO(1)O(1)O(n)O(n)O(n)O(n)O)O(n)O)O(n)O)O(n)O)O)O)O(n)O)O)O)O(n)O)O(n)O)O)O)O(n)O)O)O(n)O)O)O)O(n)Oメモリ制限狂気病…

#include
#include
#include
#include
using namespace std;
const int N=100005,M=1000005;
struct node{
    int l,r,s,t,pos;
}q[M];
int a[N];
int block[N];
bool cmp(node a,node b){
    if(block[a.l]!=block[b.l])
        return block[a.l]<block[b.l];
    return a.r<b.r;
}
int cnt[N];
int sum[N];
void Add(int x){
    if(cnt[x]==0){
        sum[block[x]]++;
    }
    cnt[x]++;
}
void Delete(int x){
    cnt[x]--;
    if(cnt[x]==0)
        sum[block[x]]--;
}
int Query(int x,int y){
    int res=0;
    if(block[y]-block[x]<=1){
        for(int i=x;i<=y;i++)
            res+=cnt[i]>0;
        return res;
    }
    for(int i=block[x]+1;i<=block[y]-1;i++)
        res+=sum[i];
    for(int i=x;block[i]==block[x];i++)
        res+=cnt[i]>0;
    for(int i=y;block[i]==block[y];i--)
        res+=cnt[i]>0;
    return res;
}
int n,m;
int ans[M];
void Read(int &x){
    x=0;
    char c=getchar();
    while(c<'0'||c>'9')
        c=getchar();
    while(c>='0'&&c<='9')
        x=x*10+c-'0',c=getchar();
}
int main()
{
    Read(n),Read(m);
    //scanf("%d%d",&n,&m);
    int S=sqrt(n);
    for(int i=1;i<=n;i++)
        block[i]=(i-1)/S+1;
    for(int i=1;i<=n;i++){
        Read(a[i]);
        //scanf("%d",&a[i]);
    }
    for(int i=1;i<=m;i++){
        Read(q[i].l),Read(q[i].r),Read(q[i].s),Read(q[i].t);
        //scanf("%d%d%d%d",&q[i].l,&q[i].r,&q[i].s,&q[i].t);
        q[i].pos=i;
    }
    sort(q+1,q+m+1,cmp);
    int l=1,r=0;
    for(int i=1;i<=m;i++){
        int ql=q[i].l,qr=q[i].r;
        while(l>ql){
            l--;
            Add(a[l]);
        }
        while(r<qr){
            r++;
            Add(a[r]);
        }
        while(l<ql){
            Delete(a[l]);
            l++;
        }
        while(r>qr){
            Delete(a[r]);
            r--;
        }
        ans[q[i].pos]=Query(q[i].s,q[i].t);
    }
    for(int i=1;i<=m;i++)
        printf("%d
",ans[i]);
}