2020-2021 ACM-ICPC, Asia Nanjing Regional Contest

发挥逐渐变好，更需继续努力。

上一场还完全没有开工，就来新的了，寄。

（某些题代码不给是因为考场代码不忍直视，然后我又不想写了

[A Ah, It’s Yesterday Once More]

solution

题面：一个的格点图，有一些袋鼠在一些格点，有些格点是墙壁。你需要给出上下左右四个操作，最终让所有袋鼠在同一个格子（撞墙会原地不动）。现有一个随机算法，每次随机向四个方向走，问如果造一张图卡掉它。

做法：搞点折线，再搞点分支就差不多了，具体直接看代码。

//2021.10.6 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const char ans[21][21]={
        "11111000111000111011",
        "00101101101101101110",
        "10110110110110110011",
        "10011011011011011010",
        "11101101101101101100",
        "10110110110110110110",
        "11011011011011011011",
        "01101101101101101101",
        "10110110110110110111",
        "10011011011011011010",
        "11101101101101101100",
        "10110110110110110110",
        "11011011011011011011",
        "01101101101101101101",
        "10110110110110110111",
        "10011011011011011000",
        "11101101101101101101",
        "10110110110110110111",
        "11011011011011011001",
        "01101110001110001111"
};
namespace MAIN{
    inline void MAIN(){
        printf("20 20\n");
        for(res i=0;i<20;i++)cout<<ans[i]<<endl;
    }
}

[B Baby’s First Suffix Array Problem]

solution

题面：给出字符串，多次询问，求区间第大后缀。

做法：

[C Certain Scientific Railgun]

solution

题面：

做法：

[D Degree of Spanning Tree]

solution

题面：个点条边的无向图，找出一棵树，使得每个点的度数都小于。

做法：我直接随机一个根，再随机边顺序，来个次就过了。时间复杂度。

[E Evil Coordinate]

solution

题面：从出发，告诉你要往上下左右分别走的步数，不能走到某个给定的点上。求一个构造方案。

做法：考虑直接走矩形，走个种，发现走过的每个点都至少有一种走法没经过过，所以有解则一定就在这些走法中了。时间复杂度。

[F Fireworks]

solution

题面：你可以花个时间准备一个烟花，的时间点燃所有烟花，一个烟花被点燃的概率是，问最小期望时间点燃一个烟花？

做法：猜测一下就是每次准备个烟花，然后点燃，没有就再点燃，而且这个是固定的。然后你推一下式子，发现是个奇怪函数的极值。但求完导就能发现这个东西的极值点是可以三分的，所以三分一下就行了。时间复杂度。

[G Go]

solution

题面：

做法：

[H Harmonious Rectangle]

solution

题面：问有多少个的矩阵存在一对，满足或者。

做法：诈骗题，不过还挺好想的。

注意到列数大于等于时，则至少第一行有一种颜色有四个，那么它们对应的下一行肯定要有两个颜色相同，所以一定都是合法的。

于是想要更好地缩小，继续考虑不合法。我们可以发现当列数为的时候，因为一定至少有两个（因为有已经结束了），所以它们对应的下面一定都是所有颜色，于是就有两列满足行行一致了，所以也全是合法的。

其他暴搜一下就好了。

[I Interested in Skiing]

solution

题面：二维平面上有若干条线段和两条直线作为障碍，从走到，不能碰到任何障碍。方向速度恒定为，方向速度可以随意调节，但其绝对值有一个上界。求最小的是多少。

做法：注意到每次肯定只走端点，把端点按排序，令表示能走到第个端点要用的最小的，转移就直接暴力从哪里来的，然后做个线段判交即可。时间复杂度。

[J Just Another Game of Stones]

solution

题面：堆石子，博弈。两种操作，一是区间取，二是区间，但问的是先手必胜的先手方案数。

做法：结论再熟悉不过了，就是异或起来是不是零。区间取也再熟悉不过了，就是，维护最小值，最小值个数，次小值即可。先手必胜也很简单，只要取到异或为即可，那么不妨设总异或和为，取第堆石子，那么条件就是，即，于是就是有多少个满足这个东西就行了。发现这东西就是看的最高位的的，于是线段树每个结点维护下每个位置的个数，其他都是可以轻松做到的了，时间复杂度。

//2021.10.6 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int N=2e5+10;
namespace MAIN{
    int n,q;
    int cnt[N<<2][30];
    int Xor[N<<2];
    int mn[N<<2],smn[N<<2],cmn[N<<2];
    inline void pushup(const res &rt){
        if(mn[rt<<1]<mn[rt<<1|1]){
            mn[rt]=mn[rt<<1],cmn[rt]=cmn[rt<<1];
            if(smn[rt<<1]<mn[rt<<1|1])smn[rt]=smn[rt<<1];
            else smn[rt]=mn[rt<<1|1];
        }
        else if(mn[rt<<1]>mn[rt<<1|1]){
            mn[rt]=mn[rt<<1|1],cmn[rt]=cmn[rt<<1|1];
            if(smn[rt<<1|1]<mn[rt<<1])smn[rt]=smn[rt<<1|1];
            else smn[rt]=mn[rt<<1];
        }
        else mn[rt]=mn[rt<<1],cmn[rt]=cmn[rt<<1]+cmn[rt<<1|1],smn[rt]=min(smn[rt<<1],smn[rt<<1|1]);
        for(res i=0;i<30;i++)cnt[rt][i]=cnt[rt<<1][i]+cnt[rt<<1|1][i];
        Xor[rt]=Xor[rt<<1]^Xor[rt<<1|1];
    }
    int tag[N<<2];
    void build(res rt,res l,res r){
        tag[rt]=-1;
        if(l==r){
            res x=read();
            mn[rt]=Xor[rt]=x,cmn[rt]=1,smn[rt]=1<<30;
            for(res i=29;~i;i--)if((x>>i)&1)cnt[rt][i]=1;
            return;
        }
        res mid=(l+r)>>1;
        build(rt<<1,l,mid),build(rt<<1|1,mid+1,r),pushup(rt);
    }
    inline void change(const res &rt,const res &x){
        if(mn[rt]>=x)return;
        for(res i=29;~i;i--)if((mn[rt]>>i)&1)cnt[rt][i]-=cmn[rt];
        if(cmn[rt]&1)Xor[rt]^=mn[rt];
        for(res i=29;~i;i--)if((x>>i)&1)cnt[rt][i]+=cmn[rt];
        mn[rt]=x;
        if(cmn[rt]&1)Xor[rt]^=x;
        tag[rt]=x;
    }
    inline void pushdown(const res &rt){
        if(tag[rt]==-1)return;
        change(rt<<1,tag[rt]),change(rt<<1|1,tag[rt]),tag[rt]=-1;
    }
    void modify(res rt,res l,res r,const res &L,const res &R,const res &x){
        if(mn[rt]>=x)return;
        if(l==r){
            for(res i=29;~i;i--)if((mn[rt]>>i)&1)cnt[rt][i]=0;
            for(res i=29;~i;i--)if((x>>i)&1)cnt[rt][i]=1;
            mn[rt]=x,Xor[rt]=x;
            return;
        }
        if(L<=l&&r<=R){
            if(smn[rt]>x){change(rt,x);return;}
        }
        pushdown(rt);
        res mid=(l+r)>>1;
        if(L<=mid)modify(rt<<1,l,mid,L,R,x);
        if(R>mid)modify(rt<<1|1,mid+1,r,L,R,x);
        pushup(rt);
    }
    int query_xor(res rt,res l,res r,const res &L,const res &R){
        if(L<=l&&r<=R)return Xor[rt];
        pushdown(rt);
        res mid=(l+r)>>1,ret=0;
        if(L<=mid)ret=query_xor(rt<<1,l,mid,L,R);
        if(R>mid)ret^=query_xor(rt<<1|1,mid+1,r,L,R);
        pushup(rt);
        return ret;
    }
    int query(res rt,res l,res r,const res &L,const res &R,const res &p){
        if(L<=l&&r<=R)return cnt[rt][p];
        pushdown(rt);
        res mid=(l+r)>>1,ret=0;
        if(L<=mid)ret=query(rt<<1,l,mid,L,R,p);
        if(R>mid)ret+=query(rt<<1|1,mid+1,r,L,R,p);
        pushup(rt);
        return ret;
    }
    inline void MAIN(){
        n=read(),q=read(),build(1,1,n);
        while(q--){
            res opt=read(),l=read(),r=read(),x=read();
            if(opt==1){
                modify(1,1,n,l,r,x);
            }
            else {
                res s=query_xor(1,1,n,l,r)^x;
                if(s==0)puts("0");
                else {
                    res ret=0;
                    for(res i=29;~i;i--)if((s>>i)){ret=query(1,1,n,l,r,i);break;}
                    printf("%d\n",ret+((x^s)<=x));
                }
            }
        }
    }
}