HDU 3911線分樹区間染色区間クエリ
5396 ワード
九野のブログ、転載は出所を明記してください:http://blog.csdn.net/acmmmm/article/details/12110463
件名:
n個の点
以下は各点の値(0または1)を表します.
m個の操作
oper[u,v] oper==1は区間のすべての値を異ならせることを表します.==0は問い合わせ区間で連続して1となる最長の長さを表します.
件名:
n個の点
以下は各点の値(0または1)を表します.
m個の操作
oper[u,v] oper==1は区間のすべての値を異ならせることを表します.==0は問い合わせ区間で連続して1となる最長の長さを表します.
#include<iostream>
#include<stdio.h>
#include<string>
#include<string.h>
#include<algorithm>
#include<set>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <math.h>
#include <queue>
#define N 100100
#define ll int
#define L(x) x<<1
#define R(x) x<<1|1
#define Mid(x,y) (x+y)>>1
using namespace std;
inline ll Min(ll a,ll b){return a>b?b:a;}
inline ll Max(ll a,ll b){return a>b?a:b;}
int a[N];//1
struct node{
int l,r;
int Win, Bin;//
int Llen, Rlen;// Llen
int Lc, Rc;//
bool lazy;
int len(){return r-l+1;}
}tree[N*8];
void change(int id){
tree[id].lazy = 0;
tree[id].Lc ^= 1;
tree[id].Rc ^= 1;
int temp = tree[id].Win; tree[id].Win = tree[id].Bin; tree[id].Bin = temp;
tree[L(id)].lazy ^= 1;
tree[R(id)].lazy ^= 1;
}
void updata_up(int id){
tree[id].Lc = tree[L(id)].Lc , tree[id].Rc = tree[R(id)].Rc ;
tree[id].Rlen = tree[R(id)].Rlen;
tree[id].Llen = tree[L(id)].Llen;
tree[id].Bin=Max(tree[L(id)].Bin, tree[R(id)].Bin);
tree[id].Win=Max(tree[L(id)].Win, tree[R(id)].Win);
if( tree[L(id)].Rc == tree[R(id)].Lc)
{
if(tree[L(id)].Rc)
tree[id].Bin = Max(tree[id].Bin, tree[L(id)].Rlen + tree[R(id)].Llen);
else
tree[id].Win = Max(tree[id].Win, tree[L(id)].Rlen + tree[R(id)].Llen);
if(tree[L(id)].Llen == tree[L(id)].len())
tree[id].Llen = tree[L(id)].len() + tree[R(id)].Llen;
if(tree[R(id)].Rlen == tree[R(id)].len())
tree[id].Rlen = tree[R(id)].len() + tree[L(id)].Rlen;
}
if(tree[id].Lc==1)tree[id].Bin=Max(tree[id].Bin, tree[id].Llen);
else tree[id].Win=Max(tree[id].Win, tree[id].Llen);
if(tree[id].Rc==1)tree[id].Bin=Max(tree[id].Bin, tree[id].Rlen);
else tree[id].Win=Max(tree[id].Win, tree[id].Rlen);
}
void Lazy(int id){
if(!tree[id].lazy)
return ;
tree[id].lazy = 0;
tree[id].Lc ^= 1;
tree[id].Rc ^= 1;
int temp = tree[id].Win; tree[id].Win = tree[id].Bin; tree[id].Bin = temp;
tree[L(id)].lazy ^= 1;
tree[R(id)].lazy ^= 1;
}
void build(int l,int r,int id){
tree[id].l = l, tree[id].r = r;
tree[id].lazy=0;
if(l == r){
tree[id].Llen=tree[id].Rlen=1;
tree[id].Lc = tree[id].Rc = a[l];
tree[id].Bin = a[l];
tree[id].Win = 1-a[l];
return ;
}
int mid = Mid(l,r);
build( l, mid, L(id));
build( mid+1, r, R(id));
updata_up(id);
}
void updata(int l, int r, int id){
if(l == tree[id].l && tree[id].r == r)
{Lazy(id); change(id); return ;}
int mid=Mid(tree[id].l, tree[id].r);
if(r <= mid) updata(l, r, L(id));
else if(mid < l) updata(l, r, R(id));
else {
updata(l, mid, L(id));
updata(mid+1, r, R(id));
}
Lazy(L(id)), Lazy(R(id));
updata_up(id);
}
int query(int l, int r, int id){
Lazy(id);
if(l == tree[id].l && tree[id].r == r)
return tree[id].Bin;
int mid=Mid(tree[id].l, tree[id].r);
int r1=0, r2=0, ans=0;
if(r <= mid) r1 = query(l, r, L(id));
else if(mid < l) r2 = query(l, r, R(id));
else {
r1 = query(l, mid, L(id));
r2 = query(mid+1, r, R(id));
if(tree[L(id)].Rc == 1 && tree[R(id)].Lc == 1)
ans = Min(mid-l+1, tree[L(id)].Rlen) + Min(r-mid, tree[R(id)].Llen) ;
r1 = Max(ans, r1);
}
ans = Max(r1, r2);
return ans;
}
int main(){
int n, que, oper, b, c;
while(~scanf("%d",&n)){
for(int i=1;i<=n;i++)scanf("%d", &a[i]);
build(1,n,1);
scanf("%d", &que);
while(que--)
{
scanf("%d %d %d", &oper, &b, &c);
if(oper)
updata(b,c,1);
else
printf("%d
", query(b,c,1));//
}
}
return 0;
}
/*
0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 1 1 0 15,16
0 0 0 0 0 1 1 1 1 1 0 0 0 0 1 1 1 0 1 0 6,18
0 0 0 0 0 1 1 1 0 0 1 1 1 1 0 1 1 0 1 0 9,15
20
0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 0 1 1 0
99
0 1 16
1 15 16
0 1 17
1 6 18
0 1 18
1 9 15
0 1 19
1 1 1
0 1 20
1 1 2
1 3 5
0 1 11
1 1 20
0 1 12
0 1 13
0 1 15
1 2 20
0 1 20
1 4 19
1 5 7
1 6 13
1 2 20
0 1 1
0 2 10
0 3 8
0 4 9
0 10 11
0 1 20
ans:
6
4
5
4
4
7
2
2
2
8
1
2
2
2
1
2
*/