题目意思为有一系列村庄,然后对一些村庄进行破坏或修复。让你求与某村庄直接或间接相连且都没有破坏的村庄数量。
对于每一个区间,用线段树维护从区间左端点开始的最大连续没破坏的村庄数量 Lx 以及以区间右端点结点的最大连续没破坏的村庄数 Rx,很容易更新这两个值及求出要求的数量。
代码:
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;
int n, m;
int const N= 50010;
struct Node{
int Lx, Rx;
int value;
}tb[N<<2];
int stack[N], top= 0;
void build( int L, int R, int rt ){
if( L== R ){
tb[rt].value= 0;
tb[rt].Lx= tb[rt].Rx=1;
return; }
int mid= (L+ R)>>1;
build( L, mid, rt<<1 );
build( mid+ 1, R, rt<<1|1 );
tb[rt].Lx= tb[rt].Rx= R- L+ 1;
}
void update( int x, int y, int L, int R, int rt ){
if( L== R ){
tb[rt].value= y;
if( y ) tb[rt].Lx= tb[rt].Rx= 0;
else tb[rt].Lx= tb[rt].Rx= 1;
return;
}
int mid= (L+ R)>>1;
if( x<= mid ) update( x, y, L, mid, rt<<1 );
else update( x, y, mid+ 1, R, rt<<1|1 );
if( tb[rt<<1].Lx== mid- L+ 1 ) tb[rt].Lx= tb[rt<<1].Lx+ tb[rt<<1|1].Lx;
else tb[rt].Lx= tb[rt<<1].Lx;
if( tb[rt<<1|1].Rx== R- mid ) tb[rt].Rx= tb[rt<<1|1].Rx+ tb[rt<<1].Rx;
else tb[rt].Rx= tb[rt<<1|1].Rx;
}
int query( int x, int L, int R, int rt ){
if( L== R ) return tb[rt].value== 0;
int mid= (L+ R)>>1;
if( x<= mid ) {
if( x> mid- tb[rt<<1].Rx ) return tb[rt<<1].Rx+ tb[rt<<1|1].Lx;
else return query( x, L, mid, rt<<1 );
}
else{
if( x<= mid+ tb[rt<<1|1].Lx ) return tb[rt<<1].Rx+ tb[rt<<1|1].Lx;
return query( x, mid+ 1, R, rt<<1|1 );
}
}
int main(){
while( scanf("%d%d",&n,&m )!= EOF ){
build( 1, n, 1 ); top= 0;
for( int i= 0; i< m; ++i ){
char str[5];
int d;
scanf("%s",str );
if( str[0]== 'D' ){
scanf("%d",&d );
update( d, 1, 1, n, 1 );
stack[++top]= d;
}
else if( str[0]== 'Q' ){
scanf("%d",&d );
printf("%d\n", query( d, 1, n, 1 ) );
}
else{
if( top== 0 ) continue;
update( stack[top--], 0, 1, n, 1 );
}
}
}
return 0;
}
分享到:
相关推荐
PKU 、POJ ACM/ICPC300多题的代码,还有各种典型问题的分类代码
ACM PKU_poj 1197 仓库问题源代码,愿与大家共享。若谁更好的代码,多谢提供。
用Java代码实现POJ(PKU)上题2494!
PKU POJ 1162 Building with Blocks PKU POJ 1162 Building with Blocks PKU POJ 1162 Building with Blocks
PKU2104的源代码,高级数据结构线段树的应用之一:找数据。
acm 1001 到1009代码,已通过验证
O(nlogn)凸包问题 poj2187
POJ1151 Atlantis的源代码,非常经典线段树应用的题目,求面积。
acm pku poj 1000 1001 1002 1003 1201
1011,1012,1013,1014,1015,1017,1026,1028,1032,1035,1041,1046,1129 1149 1154 1165 1182 1185 1190 1191 1201 1251 1273 1275 1276 1286 1322 1338 1363 1364 1401 1456 1459 1564 1579 1637 1657 1658 ...
这是我个人写的POJ上2314题的Java实现,希望对喜欢ACM的人有帮助
poj1088原代码, 这是最新的版本, 经过我们dhuACM团队合作而编写的!
pku 123 题目代码 pku acm poj
#include using namespace std; #define M 1000000 char t[M+1],p[M+1]; int lent,lenp; bool kmp(char *t,char *p) { int i,j; for(i=lenp,j=0;i;i++) { if(t[i]!=p[j]) return false;...}
“北京大学程序在线评测系统”是一个免费的公益性网上程序设计题库,网址为http://poj.grids.cn/ 及 http://acm.pku.edu.cn/JudgeOnline,它包含2000多道饶有趣味的程序设计题,题目大部分来自ACM国际大学生程序设计...
pku 2761(求区间内第k小的数) 我是用线段树去做的,好像也可用树状数组做的,稍微有一点注释在里面的^_^
poi3252,北大acm里面的题目代码。
题目分类 目前网上最全的 PKU 的 网上所有的 分类总结 祝ACM 一路顺风
PKU,POJ共301题源代码。1001 1002 1003 1004 1005 1006 1007 1008 1011 1012 1013 1014 1015 1017 1018 1019 1028 1032 1042 1046 1050 1061 1065
poj经典动态规划题目解题报告,包括经典的动态规划题目20多道,可以作为学习动态规划系统的资料,包括题目: Pku acm 1179 Polygon Pku acm 1125 Stockbroker Grapevine Pku acm 1160 post office Pku ...