2019南昌网络赛I:Yukino With Subinterval(CDQ) （树状数组套主席树）

题意：询问区间有多少个连续的段，而且这段的颜色在[L,R]才算贡献，每段贡献是1。有单点修改和区间查询。

思路：46min交了第一发树套树，T了。稍加优化多交几次就过了。

不难想到，除了L这个点，其他的点都可以只统计这一段的段首。把位置看成x，颜色看成y，就成了二维平面就矩形内点的个数，这就是裸的树套树或者CDQ了。

树套树：34**ms。

/*

2019南昌网络赛I。

询问区间有多少个连续的段，而且这段的颜色在[L,R]才算贡献，每段贡献是1。 有单点修改和区间查询。

也可以CDQ来做，常数小很多。

*/

#pragma GCC optimize(2)

#include<bits/stdc++.h>

#define ll long long

#define rep(i,a,b) for(int i=a;i<=b;i++)

using namespace std;

const int maxn=;

struct in{

    int l,r,sum;

}s[maxn*];

int a[maxn],rt[maxn],N,M,cnt;

void add(int &Now,int L,int R,int pos,int v)

{

    if(!Now) Now=++cnt; s[Now].sum+=v;

    if(L==R) return ;int Mid=(L+R)>>;

    if(pos<=Mid) add(s[Now].l,L,Mid,pos,v);

    else add(s[Now].r,Mid+,R,pos,v);

}

void Add(int x,int pos,int v)

{

    while(x<=N){

        add(rt[x],,N,pos,v);

        x+=(-x)&x;

    }

}

int query(int Now,int L,int R,int l,int r)

{

    if(!Now||s[Now].sum==) return ;

    if(l<=L&&r>=R) return s[Now].sum;

    int Mid=(L+R)>>,res=;

    if(l<=Mid) res+=query(s[Now].l,L,Mid,l,r);

    if(r>Mid) res+=query(s[Now].r,Mid+,R,l,r);

    return res;

}

int Query(int x,int L,int R)

{

    if(L>R||x==) return ;

    int res=; while(x){

        res+=query(rt[x],,N,L,R);

        x-=(-x)&x;

    } return res;

}

void read(int &x){

    x=; char c=getchar();

    while(c>''||c<'') c=getchar();

    while(c>=''&&c<='') x=x*+c-'',c=getchar();

}

int main()

{

    scanf("%d%d",&N,&M);

    rep(i,,N) {

        read(a[i]);

        if(a[i]!=a[i-]) Add(i,a[i],);

    }

    int opt,pos,L,R,x,y;

    while(M--){

        read(opt);

        if(opt==){

            read(L); read(R); read(x); read(y);

            int ans=Query(R,x,y)-Query(L-,x,y);

            if(a[L]==a[L-]&&a[L]<=y&&a[L]>=x) ans++;

            printf("%d\n",ans);

        }

        else {

            read(pos); read(x);

            if(a[pos]==x) continue;

            if(a[pos]!=a[pos-]) Add(pos,a[pos],-);

            if(pos+!=N&&a[pos+]!=a[pos]) Add(pos+,a[pos+],-);

            a[pos]=x;

            if(a[pos]!=a[pos-]) Add(pos,a[pos],);

            if(pos+!=N&&a[pos+]!=a[pos]) Add(pos+,a[pos+],);

        }

    }

    return ;

}

CDQ：700ms。

/*

2019南昌网络赛I：

*/

#include<bits/stdc++.h>

#define rep(i,a,b) for(int i=a;i<=b;i++)

using namespace std;

const int maxn=;

struct in{

    int opt,x,y,z,id;

    //opt=0是修改，否则是查询。

    //opt=1表示时间为x，查询[1,x],[y,z]的矩形面积

    //时间为第一维，x为第二维，y到z为第三维

}s[maxn<<],q[maxn<<];

int c[maxn],ans[maxn],tot,Q;

int sum[maxn],N,M;

void add(int x,int val)

{

    for(int i=x;i<=N;i+=(-i)&i) sum[i]+=val;

}

int query(int x){

    int res=;

    for(int i=x;i;i-=(-i)&i) res+=sum[i];

    return res;

}

void CDQ(int y,int z,int L,int R) //x在[y,z]区间,操作在[L,R]。 不停地对x进行分治，并把[L,R]进行相应的划分

{

    if(L>=R) return ;

    if(y>z) return ;

    if(y==z){ //特殊的一行

        rep(i,L,R) {

           if(!s[i].opt) add(s[i].y,s[i].z);

           if(s[i].opt!=) ans[s[i].id]+=s[i].opt*(query(s[i].z)-query(s[i].y-));

        }

        rep(i,L,R) if(!s[i].opt) add(s[i].y,-s[i].z);

        return ;

    }

    int Mid=(y+z)>>,F=L,C=L;

    rep(i,L,R) {

        if(s[i].x<=Mid) C++;

        if(!s[i].opt&&s[i].x<=Mid) add(s[i].y,s[i].z);

        if(s[i].opt!=&&s[i].x>Mid) ans[s[i].id]+=s[i].opt*(query(s[i].z)-query(s[i].y-));

    }

    rep(i,L,R) if(!s[i].opt&&s[i].x<=Mid) add(s[i].y,-s[i].z);

    rep(i,L,R) if(s[i].x<=Mid) q[F++]=s[i]; else q[C++]=s[i];

    rep(i,L,R) s[i]=q[i];

    CDQ(y,Mid,L,F-); CDQ(Mid+,z,F,R);

}

int main()

{

    scanf("%d%d",&N,&M);

    rep(i,,N) {

        scanf("%d",&c[i]);

        if(c[i]!=c[i-]) s[++tot]=in{,i,c[i],,};

    }

    int opt,L,R,x,y;

    rep(i,,M){

        scanf("%d",&opt);

        if(opt&){

            scanf("%d%d",&x,&y);

            if(y==c[x]) continue;

            if(c[x]!=c[x-]) s[++tot]=in{,x,c[x],-,};

            if(x<N&&c[x]!=c[x+]) s[++tot]=in{,x+,c[x+],-,};

            c[x]=y;

            if(c[x]!=c[x-]) s[++tot]=in{,x,c[x],,};

            if(x<N&&c[x]!=c[x+]) s[++tot]=in{,x+,c[x+],,};

        }

        else {

            scanf("%d%d%d%d",&L,&R,&x,&y); Q++;

            s[++tot]=in{,R,x,y,Q};

            s[++tot]=in{-,L,x,y,Q};

            if(c[L]>=x&&c[L]<=y) ans[Q]++;

        }

    }

    CDQ(,N,,tot);

    rep(i,,Q) printf("%d\n",ans[i]);

    return ;

}

巴特西

2019南昌网络赛I:Yukino With Subinterval(CDQ) （树状数组套主席树）

最新文章

热门文章