考虑线段树维护区间里已配对的括号数,左边还没配对的右括号数,右边还没配对的左括号数。 区间询问,合并两个子区间即可。 int n; char s[1000010]; struct node { int c,l,r; }o[4000010]; node merge(node l,node r) { node tt; tt.c=l.c+r.c+min(l.l,r.r); tt.l=max(0,l.l-r.r)+r.l; tt.r=l.r+max(0,r.r-l.l); return tt; } void build(int x,int l,int r) { if(l==r) { o[x].c=0; if(s[l]=='(') o[x].l=1; else o[x].r=1; return ; } int mid=(l+r)/2; build(x*2,l,mid); build(x*2+1,mid+1,r); o[x]=merge(o[x*2],o[x*2+1]); } node ask(int x,int l,int r,int tl,int tr) { if(tl<=l&&r<=tr) return o[x]; int mid=(l+r)/2; if(tr<=mid) return ask(x*2,l,mid,tl,tr); if(tl>mid) return ask(x*2+1,mid+1,r,tl,tr); return merge(ask(x*2,l,mid,tl,tr),ask(x*2+1,mid+1,r,tl,tr)); } int main() { scanf("%s",s+1); n=strlen(s+1); build(1,1,n); for(int q=read();q;q--) { int l=read(),r=read(); printf("%d\n",ask(1,1,n,l,r).c*2); } }380C
考虑黑白格地设置,令奇数的上下左右都是偶数,偶数的上下左右都是奇数。 int n,m,x; void work() { n=read();m=read(); for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { x=read(); if((i+j)%2==x%2) printf("%d ",x); else printf("%d ",x+1); } printf("\n"); } } int main() { for(int t=read();t;t--) work(); }1438C
标签:node,int,tt,mid,read,cf2000,ask,100 From: https://www.cnblogs.com/qywyt/p/16882966.html