首页 > 代码库 > POJ2892Tunnel Warfare
POJ2892Tunnel Warfare
写完之后各种调试各种TLE,第二天早上整理了下思路,重写了一遍,立马AC了;具体见注释
#include <cstdio> #include <cstring> #include <cmath> #include <algorithm> #include <climits> #include <string> #include <iostream> #include <map> #include <cstdlib> #include <list> #include <set> #include <queue> #include <stack> using namespace std; #define INF 0xfffffff #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 const int maxn=55555; int num[maxn<<1]; int sum[maxn<<2],lsum[maxn<<2],rsum[maxn<<2]; //sum数组存储连续村庄个数,lsum存储区间内从左起连续个数,rsum存储区间内从右起连续个数 void pushup(int rt,int m) { lsum[rt]=lsum[rt<<1]; rsum[rt]=rsum[rt<<1|1]; if(lsum[rt]==(m-(m>>1))) lsum[rt]+=lsum[rt<<1|1]; if(rsum[rt]==(m>>1)) rsum[rt]+=rsum[rt<<1]; sum[rt]=max(max(sum[rt<<1],sum[rt<<1|1]),rsum[rt<<1]+lsum[rt<<1|1]); } void build(int l,int r,int rt) { if(l==r) { lsum[rt]=rsum[rt]=sum[rt]=1; return ; } int m=(l+r)>>1; build(lson); build(rson); pushup(rt,r-l+1); } void update(int key,int add,int l,int r,int rt) { if(l==r) { sum[rt]=lsum[rt]=rsum[rt]=add?1:0; return ; } int m=(l+r)>>1; if(key<=m) update(key,add,lson); else update(key,add,rson); pushup(rt,r-l+1); } int query(int key,int l,int r,int rt) { if(l==r) { return sum[rt]; } int m=(l+r)>>1; int ans=0; int a=l+lsum[rt]-1;int b=r-rsum[rt]+1; if(key>=l&&key<=a) ans=lsum[rt]; if(key>=b&&key<=r) ans=max(ans,rsum[rt]); int c=m-rsum[rt<<1]+1;int d=m+lsum[rt<<1|1]; if(key>=c&&key<=d) ans=max(ans,rsum[rt<<1]+lsum[rt<<1|1]); if(ans) return ans; if(key<=m) return query(key,lson); else return query(key,rson); } int main() { int n,m,a; char str[100]; while(scanf("%d%d",&n,&m)!=EOF) { build(1,n,1); int cnt=0; while(m--) { scanf("%s",str); if(str[0]=='D') { scanf("%d",&a); update(a,0,1,n,1); num[cnt++]=a; } else if(str[0]=='R') { int t=num[--cnt]; update(t,1,1,n,1); } else { scanf("%d",&a); printf("%d\n",query(a,1,n,1)); } } } return 0; }
POJ2892Tunnel Warfare
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。