LEM4 - WHITE BLACK

Tác giả: skyvn97

Ngôn ngữ: C++

#include<cstdio>
#include<vector>
#define FOR(i,a,b) for (int i=(a),_b=(b);i<=_b;i=i+1)
#define REP(i,n) for (int i=0,_n=(n);i<_n;i=i+1)
using namespace std;
class SegmentTree {
private:
    struct Node {
        int len,left,right,range;
        Node() {
            len=left=right=range=0;
        }
        Node(int col,int len) {
            this->len=len;
            left=right=range=col==1?len:0;
        }
        bool fullSeg(void) const {
            return (left==len && right==len);
        }
        Node operator + (const Node &x) const {
            Node res;
            res.len=len+x.len;
            res.left=fullSeg()?left+x.left:left;
            res.right=x.fullSeg()?right+x.right:x.right;
            res.range=max(max(range,x.range),right+x.left);
            return (res);
        }
    };
    vector<Node> tree;
    vector<int> lazy;
    int n;
    void pushdown(int i,int l,int r) {
        if (lazy[i]<0) return;
        int m=(l+r)>>1;
        lazy[2*i]=lazy[2*i+1]=lazy[i];
        tree[2*i]=Node(lazy[i],m-l+1);
        tree[2*i+1]=Node(lazy[i],r-m);
        lazy[i]=-1;
    }
    void update(int i,int l,int r,int u,int v,int c) {
        if (l>v || r<u || l>r || v<u) return;
        if (u<=l && r<=v) {
            tree[i]=Node(c,r-l+1);
            lazy[i]=c;
            return;
        }
        pushdown(i,l,r);
        int m=(l+r)>>1;
        update(2*i,l,m,u,v,c);
        update(2*i+1,m+1,r,u,v,c);
        tree[i]=tree[2*i]+tree[2*i+1];
    }
public:
    SegmentTree() {
        n=0;
    }
    SegmentTree(int n) {
        this->n=n;
        tree.assign(4*n+7,Node());
        lazy.assign(4*n+7,-1);
        update(1,1,n,1,n,1);
    }
    void update(int l,int r,int c) {
        update(1,1,n,l,r,c);
    }
    int maxSeg(void) const {
        return (tree[1].range);
    }
};
int n,q;
void process(void) {
    scanf("%d%d",&n,&q);
    SegmentTree myit(n);
    REP(zz,q) {
        int t,l,r;
        scanf("%d",&t);
        if (t==3) printf("%d\n",myit.maxSeg());
        else {
            scanf("%d%d",&l,&r);
            myit.update(l,r,t==1);
        }
    }
}
int main(void) {
    process();
    return 0;
}

Download