線段樹維護(hù)區(qū)間取反、區(qū)間覆蓋。
拿日華哥哥的代碼對拍了好久終于AC啦。
以下是我的代碼：
/*
* Author: lee1r
* Created Time: 2011/8/21 10:04:48
* File Name: hdu3397.cpp
*/
#include<iostream>
#include<sstream>
#include<fstream>
#include<vector>
#include<list>
#include<deque>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cctype>
#include<cmath>
#include<ctime>
#define L(x) ((x)<<1)
#define R(x) ((x)<<1|1)
#define Half(x) ((x)>>1)
#define Lowbit(x) ((x)&(-(x)))
using namespace std;
const int kInf(0x7f7f7f7f);
const double kEps(1e-8);
typedef unsigned int uint;
typedef long long int64;
typedef unsigned long long uint64;
int scanf(int &num)
{
char in;
while((in=getchar())!=EOF && (in>'9' || in<'0'));
if(in==EOF) return 0;
num=in-'0';
while(in=getchar(),in>='0' && in<='9') num*=10,num+=in-'0';
return 1;
}
const int kMaxn(100007);
struct Node
{
int a,b;
int max0,lmax0,rmax0;
int max1,lmax1,rmax1;
int cnt0,cnt1;
int cover,reverse;
};
int N,M;
bool r[kMaxn];
Node tree[kMaxn<<2];
void PushDown(int node)
{
if(tree[node].cover!=-1)
{
tree[L(node)].reverse=tree[R(node)].reverse=0;
tree[L(node)].cover=tree[R(node)].cover=tree[node].cover;
if(tree[node].cover==0)
{
tree[L(node)].cnt0=tree[L(node)].max0=tree[L(node)].lmax0=tree[L(node)].rmax0=(tree[L(node)].b-tree[L(node)].a+1);
tree[L(node)].cnt1=tree[L(node)].max1=tree[L(node)].lmax1=tree[L(node)].rmax1=0;
tree[R(node)].cnt0=tree[R(node)].max0=tree[R(node)].lmax0=tree[R(node)].rmax0=(tree[R(node)].b-tree[R(node)].a+1);
tree[R(node)].cnt1=tree[R(node)].max1=tree[R(node)].lmax1=tree[R(node)].rmax1=0;
}
else
{
tree[L(node)].cnt0=tree[L(node)].max0=tree[L(node)].lmax0=tree[L(node)].rmax0=0;
tree[L(node)].cnt1=tree[L(node)].max1=tree[L(node)].lmax1=tree[L(node)].rmax1=(tree[L(node)].b-tree[L(node)].a+1);
tree[R(node)].cnt0=tree[R(node)].max0=tree[R(node)].lmax0=tree[R(node)].rmax0=0;
tree[R(node)].cnt1=tree[R(node)].max1=tree[R(node)].lmax1=tree[R(node)].rmax1=(tree[R(node)].b-tree[R(node)].a+1);
}
tree[node].cover=-1;
}
if(tree[node].reverse)
{
tree[node].reverse=0;
swap(tree[L(node)].max0,tree[L(node)].max1);
swap(tree[L(node)].lmax0,tree[L(node)].lmax1);
swap(tree[L(node)].rmax0,tree[L(node)].rmax1);
swap(tree[L(node)].cnt0,tree[L(node)].cnt1);
swap(tree[R(node)].max0,tree[R(node)].max1);
swap(tree[R(node)].lmax0,tree[R(node)].lmax1);
swap(tree[R(node)].rmax0,tree[R(node)].rmax1);
swap(tree[R(node)].cnt0,tree[R(node)].cnt1);
tree[L(node)].reverse=!tree[L(node)].reverse;
tree[R(node)].reverse=!tree[R(node)].reverse;
}
}
void PushUp(int node)
{
tree[node].max0=max(tree[L(node)].max0,tree[R(node)].max0);
tree[node].max0=max(tree[node].max0,tree[L(node)].rmax0+tree[R(node)].lmax0);
if(tree[L(node)].lmax0==tree[L(node)].b-tree[L(node)].a+1)
tree[node].lmax0=tree[L(node)].lmax0+tree[R(node)].lmax0;
else
tree[node].lmax0=tree[L(node)].lmax0;
if(tree[R(node)].rmax0==tree[R(node)].b-tree[R(node)].a+1)
tree[node].rmax0=tree[R(node)].rmax0+tree[L(node)].rmax0;
else
tree[node].rmax0=tree[R(node)].rmax0;
tree[node].max1=max(tree[L(node)].max1,tree[R(node)].max1);
tree[node].max1=max(tree[node].max1,tree[L(node)].rmax1+tree[R(node)].lmax1);
if(tree[L(node)].lmax1==tree[L(node)].b-tree[L(node)].a+1)
tree[node].lmax1=tree[L(node)].lmax1+tree[R(node)].lmax1;
else
tree[node].lmax1=tree[L(node)].lmax1;
if(tree[R(node)].rmax1==tree[R(node)].b-tree[R(node)].a+1)
tree[node].rmax1=tree[R(node)].rmax1+tree[L(node)].rmax1;
else
tree[node].rmax1=tree[R(node)].rmax1;
tree[node].cnt0=tree[L(node)].cnt0+tree[R(node)].cnt0;
tree[node].cnt1=tree[L(node)].cnt1+tree[R(node)].cnt1;
}
void Build(int node,int x,int y)
{
tree[node].a=x;
tree[node].b=y;
tree[node].cover=-1;
tree[node].reverse=0;
if(x==y)
{
tree[node].cnt0=tree[node].max0=tree[node].lmax0=tree[node].rmax0=!r[x];
tree[node].cnt1=tree[node].max1=tree[node].lmax1=tree[node].rmax1=r[x];
}
else
{
int m(Half(x+y));
Build(L(node),x,m);
Build(R(node),m+1,y);
PushUp(node);
}
}
void Modify(int node,int x,int y,int type)
{
if(x<=tree[node].a && tree[node].b<=y)
{
if(type==0)
{
tree[node].reverse=0;
tree[node].cover=0;
tree[node].cnt0=tree[node].max0=tree[node].lmax0=tree[node].rmax0=tree[node].b-tree[node].a+1;
tree[node].cnt1=tree[node].max1=tree[node].lmax1=tree[node].rmax1=0;
}
else if(type==1)
{
tree[node].reverse=0;
tree[node].cover=1;
tree[node].cnt0=tree[node].max0=tree[node].lmax0=tree[node].rmax0=0;
tree[node].cnt1=tree[node].max1=tree[node].lmax1=tree[node].rmax1=tree[node].b-tree[node].a+1;
}
else if(type==2)
{
tree[node].reverse=!tree[node].reverse;
swap(tree[node].cnt0,tree[node].cnt1);
swap(tree[node].max0,tree[node].max1);
swap(tree[node].lmax0,tree[node].lmax1);
swap(tree[node].rmax0,tree[node].rmax1);
}
}
else
{
PushDown(node);
int m(Half(tree[node].a+tree[node].b));
if(m>=x)
Modify(L(node),x,y,type);
if(m<y)
Modify(R(node),x,y,type);
PushUp(node);
}
}
int Query1(int node,int x,int y)
{
if(x<=tree[node].a && tree[node].b<=y)
return tree[node].cnt1;
PushDown(node);
int m(Half(tree[node].a+tree[node].b)),re(0);
if(m>=x)
re+=Query1(L(node),x,y);
if(m<y)
re+=Query1(R(node),x,y);
return re;
}
int Query2(int node,int x,int y)
{
if(x<=tree[node].a && tree[node].b<=y)
return tree[node].max1;
PushDown(node);
int m(Half(tree[node].a+tree[node].b));
if(m>=y)
return Query2(L(node),x,y);
if(m<x)
return Query2(R(node),x,y);
return max(max(Query2(L(node),x,m),Query2(R(node),m+1,y)),min(tree[L(node)].rmax1,m-x+1)+min(tree[R(node)].lmax1,y-m));
}
int main()
{
int T;
scanf(T);
while(T--)
{
scanf(N);
scanf(M);
for(int i=1;i<=N;i++)
{
int t;
scanf(t);
if(t)
r[i]=true;
else
r[i]=false;
}
// Input
Build(1,1,N);
// Build
while(M--)
{
int c,a,b;
scanf(c);
scanf(a);
scanf(b);
a++;b++;
if(c<=2)
Modify(1,a,b,c);
else if(c==3)
printf("%d\n",Query1(1,a,b));
else
printf("%d\n",Query2(1,a,b));
}
}
return 0;
}
posted on 2011-08-22 18:57
lee1r 閱讀(477)
評論(2) 編輯 收藏 引用 所屬分類:
題目分類：數(shù)據(jù)結(jié)構(gòu)