| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
线段树4500+MS#include<iostream>
#include<string.h>
#include<stdio.h>
using namespace std;
const int N = 16010;
int n,p;
int cmd;
int x,m;
struct Node{
int l,r;
int lmax,rmax,max;
int L;
int c;
} tr[N<<2];
void update(int rt){
int lson = rt<<1, rson = rt<<1|1;
tr[rt].lmax = tr[lson].lmax;
if(tr[lson].lmax==tr[lson].L) tr[rt].lmax+=tr[rson].lmax;
tr[rt].rmax = tr[rson].rmax;
if(tr[rson].rmax == tr[rson].L) tr[rt].rmax += tr[lson].rmax;
tr[rt].max = max(tr[lson].rmax+tr[rson].lmax,max(tr[lson].max,tr[rson].max));
}
void fill(int rt,int c){
tr[rt].c = c;
tr[rt].lmax = tr[rt].rmax = tr[rt].max = (c==1?0:tr[rt].L);
}
void push_down(int rt){
if(tr[rt].c==0) return;
fill(rt<<1,tr[rt].c);
fill(rt<<1|1,tr[rt].c);
tr[rt].c = 0;
}
void build(int rt,int l,int r){
if(l>r) return;
tr[rt].c = 0;
tr[rt].l=l,tr[rt].r = r;
tr[rt].lmax =tr[rt].rmax = tr[rt].max = r-l+1;
tr[rt].L = r-l+1;
if(l==r) return;
int mid = (l+r)>>1;
build(rt<<1,l,mid);
build(rt<<1|1,mid+1,r);
}
void insert(int c,int rt,int l,int r){
//1 enter guest -1, release guest
if(l<=tr[rt].l && r>=tr[rt].r){
tr[rt].c = c;
if(c==1) tr[rt].max = tr[rt].lmax = tr[rt].rmax = 0;
else tr[rt].max = tr[rt].lmax = tr[rt].rmax = tr[rt].L;
return;
}
push_down(rt);
int mid = (tr[rt].l+tr[rt].r)>>1;
if(l<=mid) insert(c,rt<<1,l,r);
if(r>=mid+1) insert(c,rt<<1|1,l,r);
update(rt);
}
int main()
{
scanf("%d%d",&n,&p);
build(1,1,n);//all available
tr[1].c = -1;
for(int i=0;i<p;i++){
scanf("%d",&cmd);
if(cmd<3) scanf("%d%d",&x,&m);
if(cmd==1){
insert(1,1,x,x+m-1);
}else if(cmd==2){
insert(-1,1,x,x+m-1);
}else printf("%d\n",tr[1].max);
}
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator