3226: [Sdoi2008]校门外的区间

链接

思路

  bug漫天飞。。。

  维护一颗线段树,支持区间赋值,和区间异或。因为会处理到一些方括号还是圆括号的问题,所以对于每一个下标都乘2,假设中间有一个.5即可,都变成了方括号,输出在处理一下。

  • U  [l,r]赋值为1
  • I   [0,l-1],[r+1,n]赋值为0
  • D [l,r]区间涂0
  • C [0,l-1],[r+1,n]赋值为0,[l,r]区间异或
  • S [l,r]区间异或

bug列表:乘2后从0开始,因为0*2=0,0.5*2=1,zz的居然是从2开始的。。

读入的区间并不都是一位数。。。

 #include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<iostream> using namespace std;
const int N = ; int tag[N],xr[N],ans[N];
char opt[],s[];
bool fir = true; #define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1 void pushdown(int rt) {
if (tag[rt]!=-) {
tag[rt<<] = tag[rt<<|] = tag[rt];
xr[rt<<] = xr[rt<<|] = ;
tag[rt] = -;
}
if (xr[rt]) {
xr[rt<<] ^= ;xr[rt<<|] ^= ;
xr[rt] = ;
}
}
void update(int l,int r,int rt,int L,int R,int x) {
if (L <= l && r <= R) {
if (x != -) tag[rt] = x,xr[rt] = ;
else xr[rt] ^= ;
return ;
}
pushdown(rt);
int mid = (l + r) / ;
if (L <= mid) update(lson,L,R,x);
if (R > mid) update(rson,L,R,x);
}
void query(int l,int r,int rt) {
if (l == r) {
if (tag[rt]!=-) ans[l] = tag[rt];
ans[l] ^= xr[rt];
return ;
}
pushdown(rt);
int mid = (l + r) / ;
query(lson);query(rson);
}
void get(int &L,int &R) {
char c=getchar();int flag;
while (c!='('&&c!='[') c=getchar();
scanf("%d",&L);
flag = (c=='('); L = (L*)+flag;
c = getchar();scanf("%d",&R);c = getchar();
flag = -(c!=']');R = (R*)+flag;
}
int main () { int n = ,L,R,lt;
memset(tag,-,sizeof(tag)); while (scanf("%s",opt)!=EOF) {
get(L,R); //-
if (opt[]=='U') {
update(,n,,L,R,);
}
else if (opt[]=='I') {
if (L- >= ) update(,n,,,L-,);
if (R+ <= n) update(,n,,R+,n,);
}
else if (opt[]=='D') {
update(,n,,L,R,);
}
else if (opt[]=='C') {
if (L- >= ) update(,n,,,L-,);
if (R+ <= n) update(,n,,R+,n,);
update(,n,,L,R,-);
}
else {
update(,n,,L,R,-);
}
}
query(,n,);
int pos=,flag=;
for (int i=; i<=n; i=pos+) {
pos=i;
if (!ans[i]) continue;
if (flag) printf(" ");
flag=; while (ans[pos+]) pos++;
if (i&) printf("(%d,",i/);
else printf("[%d,",i/);
if (pos&) printf("%d)",(pos+)/);
else printf("%d]",pos/);
}
if (!flag) puts("empty set");//-
return ;
}
上一篇:CentOS用yum安装X Window


下一篇:LeetCode算法题-Longest Palindrome(五种解法)