Codeforces717F

Codeforces717F题解

题解：

• 以下根据网上大佬们的博客。
• 消除完一个区间肯定有一大堆方法，不妨考虑其中一种：
• 先前两个之间反复横跳，消除光第一个，然后再消除第二个，直到消除完。
• 然后我们可以根据这个列出不等式和方程：
• $$a_l\ge1\\a_{l+1}-a_l\ge0\\a_{l+2}-a_{l+1}+a_l\ge1\\\cdots\\a_r-a_{r-1}+\cdots\ge[(r-l+1)\equiv1(mod2)]\\a_r-a_{r-1}+\cdots=(r-l+1)mod2$$
• 然后我们令$d_i=a_i-a_{i-1}+\cdots$，用线段树维护即可。

代码：

#include <bits/stdc++.h>
#define gc getchar()
#define ll long long
#define inf 1e9
#define N 200009
#define mid (l+r>>1)
#define root 1,1,n
#define lc cur<<1
#define rc lc|1
#define lson lc,l,mid
#define rson rc,mid+1,r
#define now cur,l,r
using namespace std;
int n,m,a[N],bit[N],b[N],tg[N<<2][2],Min[N<<2][2];
int read()
{
	int x=1;
	char ch;
	while (ch=gc,ch<'0'||ch>'9') if (ch=='-') x=-1;
	int s=ch-'0';
	while (ch=gc,ch>='0'&&ch<='9') s=s*10+ch-'0';
	return s*x;
}
void up(int cur,int l,int r)
{
    Min[cur][0]=min(Min[lc][0],Min[rc][0]);
    Min[cur][1]=min(Min[lc][1],Min[rc][1]);
}
void down(int cur,int l,int r)
{
    for (int k=0;k<2;k++)
        if (tg[cur][k])
        {
            tg[lc][k]+=tg[cur][k],tg[rc][k]+=tg[cur][k];
            Min[lc][k]+=tg[cur][k],Min[rc][k]+=tg[cur][k];
            tg[cur][k]=0;
        }
}
void build(int cur,int l,int r)
{
    if (l==r)
    {
        Min[cur][l&1]=b[l];
        Min[cur][l&1^1]=inf;
        tg[cur][0]=tg[cur][1]=0;
        return;
    }
    build(lson);
    build(rson);
    up(now);
}
void ins(int cur,int l,int r,int L,int R,int y,int k)
{
    if (L>R) return;
    if (L<=l&&R>=r)
    {
        tg[cur][k]+=y;
        Min[cur][k]+=y;
        return;
    }
    down(now);
    if (L<=mid) ins(lson,L,R,y,k);
    if (R>mid) ins(rson,L,R,y,k);
    up(now);
}
int qry(int cur,int l,int r,int L,int R,int k)
{
    if (L<=l&&R>=r) return Min[cur][k];
    down(now);
    int ret=inf;
    if (L<=mid) ret=min(ret,qry(lson,L,R,k));
    if (R>mid) ret=min(ret,qry(rson,L,R,k));
    return ret;
}
int qry(int cur,int l,int r,int x,int k)
{
    if (x==0) return 0;
    if (l==r) return Min[cur][k];
    down(now);
    if (x<=mid) return qry(lson,x,k);
    else return qry(rson,x,k);
}
int main()
{
    n=read();
    for (int i=1;i<=n;i++) a[i]=read();
    m=read();
    for (int i=1;i<=n;i++) b[i]=a[i]-b[i-1];
    build(root);
    while (m--)
    {
        int op=read();
        if (op==1)
        {
            int l=read()+1,r=read()+1,k=read();
            ins(root,l,r,k,l&1);
            if ((r-l+1)&1) ins(root,r+1,n,k,l&1),ins(root,r+1,n,-k,l&1^1);
        }
        else
        {
            int l=read()+1,r=read()+1;
            if ((r-l+1)&1)
            {
                int ret=qry(root,l-1,(l-1)&1);
                int ret1=qry(root,l,r,r&1)+ret;
                int ret2=qry(root,l,r,r&1^1)-ret;
                int ret3=qry(root,r,r&1)+ret;
                if (ret3==1&&ret1>=1&&ret2>=0) puts("1");
                else puts("0");
            }
            else
            {
                int ret=qry(root,l-1,(l-1)&1);
                int ret1=qry(root,l,r,r&1)-ret;
                int ret2=qry(root,l,r,r&1^1)+ret;
                int ret3=qry(root,r,r&1)-ret;
                if (ret3==0&&ret1>=0&&ret2>=1) puts("1");
                else puts("0");
            }
        }
    }
	return 0;
}