題意：給一個由0,1組成的序列，有兩種操作，一種是翻轉給定區間的數(0->1,1->0)，另一種是查詢給定區間內由1組成的子串的最大長度。重點在區間合並和延遲標記。
#include #include #include #include #include #include #include #include #include #include #define INF 0x3fffffff using namespace std; const int N=100010; struct Node { int l,r,lsum0,rsum0,msum0,lsum1,rsum1,msum1; int flag;//0不用翻轉，1用 int Mid(){ return (l+r)/2; } }tree[4*N]; int a[N]; //合並左右子樹 void pushUp(int rt) { int ll=tree[rt*2].r-tree[rt*2].l+1; int rl=tree[rt*2+1].r-tree[rt*2+1].l+1; //1的從左開始最大連續數 tree[rt].lsum1=tree[rt*2].lsum1; //若等於左子樹長度，就要加上右子樹左邊最大 if(tree[rt*2].lsum1==ll){ tree[rt].lsum1+=tree[rt*2+1].lsum1; } //同理，1的從右開始最大連續數 tree[rt].rsum1=tree[rt*2+1].rsum1; if(tree[rt*2+1].rsum1==rl){ tree[rt].rsum1+=tree[rt*2].rsum1; } //此區間的最大子串要麼在中間，要麼從左開始，要麼從右開始，所以最大子串為三種情況最大值。 tree[rt].msum1=max(max(tree[rt*2].msum1,tree[rt*2+1].msum1),tree[rt*2].rsum1+tree[rt*2+1].lsum1); tree[rt].lsum0=tree[rt*2].lsum0; if(tree[rt*2].lsum0==ll){ tree[rt].lsum0+=tree[rt*2+1].lsum0; } tree[rt].rsum0=tree[rt*2+1].rsum0; if(tree[rt*2+1].rsum0==rl){ tree[rt].rsum0+=tree[rt*2].rsum0; } tree[rt].msum0=max(max(tree[rt*2].msum0,tree[rt*2+1].msum0),tree[rt*2].rsum0+tree[rt*2+1].lsum0); } //交換 void Swap(int rt) { swap(tree[rt].lsum0,tree[rt].lsum1); swap(tree[rt].rsum0,tree[rt].rsum1); swap(tree[rt].msum0,tree[rt].msum1); } //從父節點向下更新(lazy) void pushDown(int rt) { if(tree[rt].flag==1){ tree[rt*2].flag^=1; tree[rt*2+1].flag^=1; tree[rt].flag=0; Swap(rt*2); Swap(rt*2+1); } } void build(int rt,int l,int r) { tree[rt].l=l;tree[rt].r=r;tree[rt].flag=0; //初始化每個葉子節點 if(l==r){ if(a[l]==0){ tree[rt].lsum0=tree[rt].rsum0=tree[rt].msum0=1; tree[rt].lsum1=tree[rt].rsum1=tree[rt].msum1=0; } else if(a[l]==1){ tree[rt].lsum0=tree[rt].rsum0=tree[rt].msum0=0; tree[rt].lsum1=tree[rt].rsum1=tree[rt].msum1=1; } return; } int mid=(l+r)/2; build(2*rt,l,mid); build(2*rt+1,mid+1,r); pushUp(rt); } void update(int rt,int l,int r) { if(tree[rt].l==l&&tree[rt].r==r){ tree[rt].flag^=1; Swap(rt); return; } //更新子樹 pushDown(rt); if(r<=tree[rt].Mid()){ update(2*rt,l,r); } else if(l>tree[rt].Mid()){ update(2*rt+1,l,r); } else{ update(2*rt,l,tree[rt].Mid()); update(2*rt+1,tree[rt].Mid()+1,r); } //向上合並更新 pushUp(rt); } int query(int rt,int l,int r) { if(tree[rt].l==l&&tree[rt].r==r) { return tree[rt].msum1; } pushDown(rt); int ans; if(r<=tree[rt].Mid()){ ans=query(rt*2,l,r); } else if(l>tree[rt].Mid()){ ans=query(2*rt+1,l,r); } else{ int lr=query(2*rt,l,tree[rt].Mid()); int rr=query(2*rt+1,tree[rt].Mid()+1,r); int a=tree[rt*2].rsum1; if(a>tree[rt*2].r-l+1) a=tree[rt*2].r-l+1; int b=tree[rt*2+1].lsum1; if(b>r-tree[rt*2+1].l+1) b=r-tree[rt*2+1].l+1; ans=max(max(lr,rr),a+b); } pushUp(rt); return ans; } int main() { //freopen(d:\Test.txt,r,stdin); int n; while(scanf(%d,&n)!=EOF){ for(int i=1;i<=n;i++) scanf(%d,&a[i]); build(1,1,n); int m; scanf(%d,&m); while(m--){ int op,l,r; scanf(%d%d%d,&op,&l,&r); if(op==0){ cout<
POJ訓練計劃1177_Picture(掃描線/線段樹+離散
【Qt】2.3 使用Qt設計師來創建對話框，2.3qt安裝完
筆試題31. LeetCode OJ (18)
不相交集合（並查集） 不相交集合（兩集合中沒
對於數組和多維數組的內容這裡就不再討論了，前面的
Gone Fishing Time Lim
