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;
}