题解 P4991 【愤怒的XiaoX】

ztz11 · 2018-11-04 11:45:19 · 题解

思路：

这道题其实就是一道双Lazy线段树裸题

因为我们知道，当k一定时，取反偶数次最后k位等于不取反

同理，当k一定时，翻转偶数次最后k位等于不取反

我们使用双Lazy分别存下这两个东西

同时一直对2取模

同时我们使用标记永久化

向下传参Lazy

单点查询到这个点时，判断是否需要取反即可

取反和翻转是位运算基本知识

大家可以看代码

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define rij register int j
#define rii register int i
#define rs 65536
using namespace std;
struct tree{
    int fz,qf,val;
}x[250005];
int n,k,q,t,bs[50];
void ycl()
{
    bs[0]=1;
    for(rii=1;i<=25;i++)
    {
        bs[i]=bs[i-1]*2;
    }
}
void cf(int val)
{
    unsigned int kkk=val;
    while(kkk!=0)
    {
        cout<<kkk%2<<" ";
        kkk/=2;
    }
    cout<<endl;
}
int qf(int val)
{
    int bs=(1<<k);
    int ltt=val%bs;
    val-=ltt;
    ltt=-ltt;
    ltt--;
    unsigned kkk=ltt;
    kkk%=bs;
    return val+kkk;
}
int fz(int val)
{
    int bis=(1<<k);
    int ltt=val%bis;
    int v=0;
    val-=ltt;
    for(rii=1;i<=k;i++)
    {
        v+=(ltt%2)*bs[k-i];
        ltt/=2;
    }
    return val+v;
}
void add(int wz,int nl,int nr,int val,int bh)
{
    if(wz==nl&&wz==nr)
    {
        x[bh].val=val;
        return;
    }
    int mid=(nl+nr)/2;
    if(wz<=mid)
    {
        add(wz,nl,mid,val,bh*2);
    }
    else
    {
        add(wz,mid+1,nr,val,bh*2+1);
    }
}
void change1(int l,int r,int nl,int nr,int bh)
{
    if(l<nl)
    {
        l=nl;
    }
    if(r>nr)
    {
        r=nr;
    }
    if(l==nl&&r==nr)
    {
        x[bh].qf++;
        x[bh].qf%=2;
        return;
    }
    int mid=(nl+nr)/2;
    if(l<=mid)
    {
        change1(l,r,nl,mid,bh*2);
    }
    if(r>mid)
    {
        change1(l,r,mid+1,nr,bh*2+1);
    }
}
void change2(int l,int r,int nl,int nr,int bh)
{
    if(l<nl)
    {
        l=nl;
    }
    if(r>nr)
    {
        r=nr;
    }
    if(l==nl&&r==nr)
    {
        x[bh].fz++;
        x[bh].fz%=2;
        return;
    }
    int mid=(nl+nr)/2;
    if(l<=mid)
    {
        change2(l,r,nl,mid,bh*2);
    }
    if(r>mid)
    {
        change2(l,r,mid+1,nr,bh*2+1);
    }
}
int query(int wz,int nl,int nr,int bh,int lazy1,int lazy2)
{
    lazy1%=2;
    lazy2%=2;
    if(wz==nl&&wz==nr)
    {
        lazy1+=x[bh].qf;
        lazy2+=x[bh].fz;
        int ltt=x[bh].val;
        if(lazy1==1)
        {
            ltt=qf(ltt);
        }
        if(lazy2==1)
        {
            ltt=fz(ltt);
        }
        return ltt;
    }
    int mid=(nl+nr)/2;
    if(wz<=mid)
    {
        return query(wz,nl,mid,bh*2,lazy1+x[bh].qf,lazy2+x[bh].fz);
    }
    else
    {
        return query(wz,mid+1,nr,bh*2+1,lazy1+x[bh].qf,lazy2+x[bh].fz);
    }
}
void pd(int wz,int l,int r)
{
    if(l==r)
    {
        if(x[wz].fz!=0)
        {
            x[wz].fz=0;
            x[wz].val=fz(x[wz].val);
        }
        if(x[wz].qf!=0)
        {
            x[wz].qf=0;
            x[wz].val=qf(x[wz].val);
        }
        return;
    }
    if(x[wz].fz!=0)
    {
        x[wz*2].fz++;
        x[wz*2].fz%=2;
        x[wz*2+1].fz++;
        x[wz*2+1].fz%=2;
    }
    if(x[wz].qf!=0)
    {
        x[wz*2].qf++;
        x[wz*2].qf%=2;
        x[wz*2+1].qf++;
        x[wz*2+1].qf%=2;
    }
    x[wz].qf=0;
    x[wz].fz=0;
    int mid=(l+r)/2;
    pd(wz*2,l,mid);
    pd(wz*2+1,mid+1,r);
}
int main()
{
//     freopen("XiaoX10.in","r",stdin);
//     freopen("XiaoX10.out","w",stdout);
    ycl();
    scanf("%d%d",&n,&t);
    for(rii=1;i<=n;i++)
    {
        int val;
        scanf("%d",&val);
        add(i,1,rs,val,1);
    }
    for(rii=1;i<=t;i++)
    {
        if(i!=1)
        {
            pd(1,1,rs);
        }
        scanf("%d%d",&q,&k);
        int pid,l,r,wz;
        for(rij=1;j<=q;j++)
        {
            scanf("%d",&pid);
            if(pid==1)
            {
                scanf("%d%d",&l,&r);
                change1(l,r,1,rs,1);
            }
            if(pid==2)
            {
                scanf("%d%d",&l,&r);
                change2(l,r,1,rs,1);
            }
            if(pid==3)
            {
                scanf("%d",&wz);
                int ltt=query(wz,1,rs,1,0,0);
                printf("%d\n",ltt);
            }
        }
    }
    k=4;
}