???????1 .? ? ( - > 1? ,? )? - > -1;

? ? ? ? 先想前綴和，求出l，r中的最小值，如果最小值小于l-1的前綴和，那么說明有某個點的 ) 大于 ( 數(shù)量 不滿足條件；

? ? ? ? 用線段樹優(yōu)化區(qū)間修改和區(qū)間查詢；

?2 .? ? ?隊友說，可以直接算一個區(qū)間經(jīng)過化簡之后形成的) ( 中的（ 數(shù)量和 ）的數(shù)量 ，可以區(qū)間更新；

?一 ：?

#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<vector> #include<set> using namespace std;typedef long long LL; typedef pair<int,int> PII; const int N=2e5+10,mod=998244353;int tr[N<<4],lazy[N<<4],a[N]; char c[N]; int dis(char c){return c=='('?1:-1;}void push_up(int u){tr[u]=min(tr[u<<1],tr[u<<1|1]);return ;} void add_tage(int u,int f){tr[u]+=f;lazy[u]+=f;return ;} void push_down(int u) {if(!lazy[u])return ;add_tage(u<<1,lazy[u]);add_tage(u<<1|1,lazy[u]);lazy[u]=0;return ; } void build(int u,int l,int r) {if(l==r){tr[u]=a[l];return ;}int mid=l+r>>1;build(u<<1,l,mid);build(u<<1|1,mid+1,r);push_up(u); }void modify(int u,int l,int r,int L,int R,int f) {if(L<=l&&R>=r){add_tage(u,f);return ;}push_down(u);int mid=l+r>>1;if(L<=mid)modify(u<<1,l,mid,L,R,f);if(R>mid)modify(u<<1|1,mid+1,r,L,R,f);push_up(u); }int quary(int u,int l,int r,int L,int R) {if(L<=l&&R>=r)return tr[u];push_down(u);int mid=l+r>>1,x=0x3f3f3f3f;if(L<=mid)x=min(x,quary(u<<1,l,mid,L,R));if(R>mid)x=min(x,quary(u<<1|1,mid+1,r,L,R));return x; }int main() {int n,q;scanf("%d%d%s",&n,&q,c+1);for(int i=1;i<=n;i++)a[i]=a[i-1]+dis(c[i]);build(1,1,n);while(q--){int x,l,r;scanf("%d%d%d",&x,&l,&r);if(x==1){if(c[l]==c[r])continue;swap(c[l],c[r]);int f=-2;if(c[l]=='(')f=2;modify(1,1,n,l,r-1,f);} else{int b=l>1?quary(1,1,n,l-1,l-1):0;if(quary(1,1,n,r,r)==b&&b==quary(1,1,n,l,r))printf("Yes\n");else printf("No\n");}}return 0; }

二 ：?

#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<vector> #include<set> using namespace std;typedef long long LL; typedef pair<int,int> PII; const int N=2e5+10,mod=998244353;int tr[N<<4][2]; char c[N]; int dis(char c){return c=='('?1:0;}void push_up(int x[],int a[],int b[]) {x[1]=b[1];x[0]=a[0];x[a[1]>b[0]]+=abs(a[1]-b[0]);}void build(int u,int l,int r,int x) {if(l==r){tr[u][dis(c[x])]=1;tr[u][!dis(c[x])]=0;return ;}int mid=l+r>>1;if(x<=mid)build(u<<1,l,mid,x);else build(u<<1|1,mid+1,r,x);push_up(tr[u],tr[u<<1],tr[u<<1|1]); }void quary(int u,int l,int r,int L,int R,int ans[]) {if(L<=l&&R>=r){int x[2]={0,0};push_up(ans,x,tr[u]);return ;}int mid=l+r>>1,x[2][2]={{0,0},{0,0}};if(L<=mid)quary(u<<1,l,mid,L,R,x[0]);if(R>mid)quary(u<<1|1,mid+1,r,L,R,x[1]);push_up(ans,x[0],x[1]);return ; }int main() {int n,q;scanf("%d%d%s",&n,&q,c+1);for(int i=1;i<=n;i++)build(1,1,n,i);while(q--){int x,l,r;scanf("%d%d%d",&x,&l,&r);if(x==1){if(c[l]==c[r])continue;swap(c[l],c[r]);build(1,1,n,l);build(1,1,n,r);} else{int a[2]={0,0};quary(1,1,n,l,r,a);if(!a[0]&&!a[1])printf("Yes\n");else printf("No\n");}}return 0; }

總結(jié)

以上是生活随笔為你收集整理的F - Parenthesis Checking的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。