题解

2 条题解

  • 1
    @ 2025-06-10 18:16:34
    #include<bits/stdc++.h>
    using namespace std;
    const int MAXN=1001000,MAXB=229,MAXP=19;
    struct segtree
    {
        int sum[MAXP],lazy1,lazy1a,lazy1b,lazy2,l,r,len;
    };
    //lazy1 是覆盖,lazy2 是区间异或。 
    //lazy1a 和 lazy1b 的意思是:按照 abababab... 的顺序将 lazy1a(b) 放入区间。 
    segtree a[MAXN*4+1];
    int book[MAXB],rec[MAXP],work[MAXP],rx,ry,tmap[MAXB][MAXB],tag[MAXB],m,n,q,w[MAXP];
    void pushup(int x)
    {
        int i;
        for(i=1;i<=16;i++)
        {
            a[x].sum[i]=a[x*2].sum[i]+a[x*2+1].sum[i];
        }
        return;
    }
    void pushdown(int x)
    {
        int i;
        if(a[x].lazy1!=0)
        {
            for(i=1;i<=16;i++)
            {
                a[x*2].sum[i]=a[x*2+1].sum[i]=0;
            }
            a[x*2].sum[book[a[x].lazy1a]]=(a[x*2].len+1)/2;
            a[x*2].sum[book[a[x].lazy1b]]=a[x*2].len/2;
            a[x*2].lazy1=1;
            a[x*2].lazy2=0;
            a[x*2].lazy1a=a[x].lazy1a;
            a[x*2].lazy1b=a[x].lazy1b;
            if(a[x*2].len%2==1)//如果左端点的长度为奇数,那么右端点的第一个数就是左端点的第二个数。 
            {
                swap(a[x].lazy1a,a[x].lazy1b);
            }
            a[x*2+1].sum[book[a[x].lazy1a]]=(a[x*2+1].len+1)/2;
            a[x*2+1].sum[book[a[x].lazy1b]]=a[x*2+1].len/2;
            a[x*2+1].lazy1=1;
            a[x*2+1].lazy2=0;
            a[x*2+1].lazy1a=a[x].lazy1a;
            a[x*2+1].lazy1b=a[x].lazy1b;
            a[x].lazy1=0;
        }
        if(a[x].lazy2!=0)
        {
            for(i=1;i<=16;i++)
            {
                w[i]=a[x*2].sum[book[rec[i]^a[x].lazy2]];
            }
            for(i=1;i<=16;i++)
            {
                a[x*2].sum[i]=w[i];
            }
            a[x*2].lazy2^=a[x].lazy2;
            for(i=1;i<=16;i++)
            {
                w[i]=a[x*2+1].sum[book[rec[i]^a[x].lazy2]];
            }
            for(i=1;i<=16;i++)
            {
                a[x*2+1].sum[i]=w[i];
            }
            a[x*2+1].lazy2^=a[x].lazy2;
            a[x].lazy2=0;
        }
        return;
    }
    void build(int x,int l,int r)
    {
        a[x].l=l;
        a[x].r=r;
        a[x].len=r-l+1;
        if(l==r)
        {
            if(l%2==1)
            {
                a[x].sum[book[work[1]]]=1;
            }
            else
            {
                a[x].sum[book[0]]=1;
            }
            return;
        }
        int mid=(l+r)/2;
        build(x*2,l,mid);
        build(x*2+1,mid+1,r);
        pushup(x);
        return;
    }
    void inc1(int x,int l,int r,int ca,int cb)
    {
        if(l>r)
        {
            return;
        }
        int i;
        if(a[x].l==l&&a[x].r==r)
        {
            for(i=1;i<=16;i++)
            {
                a[x].sum[i]=0;
            }
            a[x].sum[book[ca]]=(a[x].len+1)/2;
            a[x].sum[book[cb]]=a[x].len/2;
            a[x].lazy1=1;
            a[x].lazy2=0;
            a[x].lazy1a=ca;
            a[x].lazy1b=cb;
            return;
        }
        pushdown(x);
        int mid=(a[x].l+a[x].r)/2;
        if(l<=mid)
        {
            inc1(x*2,l,min(mid,r),ca,cb);
        }
        if(r>=mid+1)
        {
            if(l<=mid&&(a[x*2].r-l+1)%2==1)//如果左区间长度为奇数,那么右区间的第一个数就是左端点的第二个数。 
            {
                swap(ca,cb);
            }
            inc1(x*2+1,max(l,mid+1),r,ca,cb);
        }
        pushup(x);
        return;
    }
    void inc2(int x,int l,int r,int c)
    {
        if(l>r)
        {
            return;
        }
        int i;
        if(a[x].l==l&&a[x].r==r)
        {
            for(i=1;i<=16;i++)
            {
                w[i]=a[x].sum[book[rec[i]^c]];
            }
            for(i=1;i<=16;i++)
            {
                a[x].sum[i]=w[i];
            }
            a[x].lazy2^=c;
            return;
        }
        pushdown(x);
        int mid=(a[x].l+a[x].r)/2;
        if(l<=mid)
        {
            inc2(x*2,l,min(mid,r),c);
        }
        if(r>=mid+1)
        {
            inc2(x*2+1,max(l,mid+1),r,c);
        }
        pushup(x);
        return;
    }
    int query1(int x,int p)
    {
        if(p==0)
        {
            return 0;
        }
        int i;
        if(a[x].l==p&&a[x].r==p)
        {
            for(i=1;i<=16;i++)
            {
                if(a[x].sum[i]!=0)
                {
                    return rec[i];
                }
            }
            return 0;
        }
        pushdown(x);
        int mid=(a[x].l+a[x].r)/2;
        if(p<=mid)
        {
            return query1(x*2,p);
        }
        if(p>=mid+1)
        {
            return query1(x*2+1,p);
        }
        return 0;
    }
    int query2(int x,int l,int r,int c)
    {
        if(l>r)
        {
            return 0;
        }
        if(a[x].l==l&&a[x].r==r)
        {
            return a[x].sum[book[c]];
        }
        pushdown(x);
        int mid=(a[x].l+a[x].r)/2,ans=0;
        if(l<=mid)
        {
            ans+=query2(x*2,l,min(r,mid),c);
        }
        if(r>=mid+1)
        {
            ans+=query2(x*2+1,max(l,mid+1),r,c);
        }
        return ans;
    }
    void dfs(int x,int c)
    {
        if(x>rx+ry)
        {
            if(tag[c]==0)
            {
                tag[c]=1;
                m++;
                book[c]=m;
                rec[m]=c;
            }
            return;
        }
        dfs(x+1,c);
        dfs(x+1,c^work[x]);
        return;
    }
    void init()
    {
        int i,j,t=1;
        for(i=1;i<=rx;i++)
        {
            for(j=1;j<=ry;j++)
            {
                tmap[i][j]=t;
                t*=2;
            }
        }
        t=1;
        for(i=1;i<=rx;i++)
        {
            for(j=1;j<=ry;j++)
            {
                work[t]+=tmap[i][j];
            }
            t++;
        }
        for(j=1;j<=ry;j++)
        {
            for(i=1;i<=rx;i++)
            {
                work[t]+=tmap[i][j];
            }
            t++;
        }
        dfs(1,0);
        return;
    }
    int main()
    {
    //  freopen("P5232.in","r",stdin);
    //  freopen("P5232.out","w",stdout);
        int i,j,T,t,t1,t2,t3,ta,tb,opt;
        scanf("%d%d",&rx,&ry);
        init();
        T=0;
        for(i=1;i<=rx;i++)
        {
            for(j=1;j<=ry;j++)
            {
                scanf("%d",&t);
                T+=t*tmap[i][j];
            }
        }
        scanf("%d%d",&n,&q);
        build(1,1,n);
        for(i=1;i<=q;i++)
        {
            scanf("%d%d%d",&opt,&ta,&tb);
            if(opt==0)
            {
                t1=query1(1,ta-1);
                t2=query1(1,ta);
                inc1(1,ta,ta,work[tb]^t1,t1);
                t3=query1(1,ta);
                inc2(1,ta+1,n,t2^t3);
            }
            else if(opt==1)
            {
                printf("%d\n",query2(1,ta,tb,T));
            }
            else
            {
                scanf("%d",&t);
                t1=query1(1,ta-1);
                t2=query1(1,tb);
                inc1(1,ta,tb,work[t]^t1,t1);
                t3=query1(1,tb);
                inc2(1,tb+1,n,t2^t3);
            }
        }
        return 0;
    }
    
  • 0
    @ 2015-05-31 17:09:38

    帮忙看看,哪里错啦,怎么一个点也不过,超时!!也

    #include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<cmath>
    #include<algorithm>
    #include<vector>
    #include<queue>
    #include<cstdlib>
    using namespace std;
    int rx,ry,n,m,t=1;
    int sum[1000001],b[1000001];
    int w[3][4],map[3][4];
    void change(int d,int x)
    {
    int k;
    bool flag;
    b[d]=x;
    for(int l=1;l<=n;l++)
    {
    flag=true;
    if(b[l]>rx)
    {
    k=b[l]-rx;
    for(int i=1;i<=rx;i++)
    w[i][k]=1-w[i][k];
    }else
    {
    k=b[l];
    for(int i=1;i<=ry;i++)
    w[k][i]=1-w[k][i];
    }
    for(int i=1;i<=rx;i++)
    for(int j=1;j<=ry;j++)
    if(w[i][j]!=map[i][j])
    {
    flag=false;
    break;
    }
    if(flag)
    sum[l]=sum[l-1]+1;
    else sum[l]=sum[l-1];

    /* for(int i=1;i<=rx;i++)
    {
    for(int j=1;j<=ry;j++)
    printf("%d",w[i][j]);
    printf("\n");
    }
    printf("\n");*/
    }

    }
    void fchange(int l,int r,int x)
    {
    int k;
    bool flag;
    for(int i=l;i<=r;i++)
    b[i]=x;
    for(int g=1;g<=n;g++)
    {

    flag=true;
    if(b[g]>rx)
    {
    k=b[g]-rx;
    for(int i=1;i<=rx;i++)
    w[i][k]=1-w[i][k];
    }else
    {
    k=b[l];
    for(int i=1;i<=ry;i++)
    w[k][i]=1-w[k][i];
    }
    ///////////
    for(int i=1;i<=rx;i++)
    for(int j=1;j<=ry;j++)
    if(w[i][j]!=map[i][j])
    {
    flag=false;
    break;
    }
    if(flag)
    sum[g]=sum[g-1]+1;
    }

    }
    int main()
    {
    freopen("p1957.in","r",stdin);
    scanf("%d%d",&rx,&ry);
    for(int i=1;i<=rx;i++)
    for(int j=1;j<=ry;j++)
    scanf("%d",&map[i][j]);
    scanf("%d%d",&n,&m);
    bool flag=true;
    for(int i=1;i<=n;i++) b[i]=1;
    //////////
    for(int i=1;i<=rx;i++)
    for(int j=1;j<=ry;j++)
    if(w[i][j]!=map[i][j])
    {
    flag=false;
    break;
    }
    if(flag)
    for(int i=1;i<=n;i+=2)
    {
    sum[i+1]=sum[i-1]+1;
    sum[i]=sum[i-1];
    }
    if(n%2==1)
    for(int i=1;i<=ry;i++)
    w[1][i]=1;
    for(int i=1;i<=rx;i++)
    for(int j=1;j<=ry;j++)
    if(w[i][j]!=map[i][j])
    {
    flag=false;
    break;
    }
    if(flag)
    for(int i=1;i<=n;i+=2)
    {
    sum[i]=sum[i-1]+1;
    sum[i+1]=sum[i];
    }
    ///////////
    int f,d,x,y,l,r;
    for(int k=1;k<=m;k++)
    {
    memset(w,0,sizeof(w));
    scanf("%d",&f);
    if(f==1)
    {
    scanf("%d%d",&x,&y);
    printf("%d\n",sum[y]-sum[x-1]);
    }
    if(f==0)
    {
    scanf("%d%d",&d,&x);
    change(d,x);
    }
    if(f==2)
    {
    scanf("%d%d%d",&l,&r,&x);
    fchange(l,r,x);
    }
    }
    return 0;
    }

    • @ 2021-07-19 16:17:13

      才能卖出那么聪明你吃没吃你吃没吃那场面

    • @ 2021-07-21 08:40:09

      开o,开一百万个o

      #pragma GCC optimize(3)
      #pragma GCC optimize(2)
      #pragma GCC optimize("-Ofast")
      __attribute__((optimize("-O3")))
      
  • 1

信息

ID
1957
难度
8
分类
(无)
标签
递交数
69
已通过
8
通过率
12%
被复制
2
上传者