結果

問題 No.1802 Range Score Query for Bracket Sequence
ユーザー smiken_61
提出日時 2022-02-13 17:34:11
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 335 ms / 2,000 ms
コード長 10,748 bytes
コンパイル時間 2,050 ms
コンパイル使用メモリ 171,044 KB
実行使用メモリ 13,352 KB
最終ジャッジ日時 2024-06-30 02:22:57
合計ジャッジ時間 7,031 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 24
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

    #include <bits/stdc++.h>
 //   #include <atcoder/all>
     
     
     
     
  //  using namespace atcoder;
     
     
    // tabaicho see https://boostjp.github.io/tips/multiprec-int.html   
    // #include <boost/multiprecision/cpp_int.hpp>
     
    // using namespace boost::multiprecision;
     
    // cpp_int
    // int128_t
    // int256_t
    // int512_t
    // int1024_t
     
    // uint128_t
    // uint256_t
    // uint512_t
    // uint1024_t
     
     
    #define int long long
     #define inf  1000000007
    // #define inf  998244353
     
     #define pa pair<int,int>
     #define ppa pair<pa,pa>
     #define ll long long
     #define PI 3.14159265358979323846
     #define  mp make_pair
     #define  pb push_back
     #define EPS (1e-8)
     
          using namespace std;
                                              
     int dx[8]={0,1,0,-1,1,1,-1,-1};
     int dy[8]={1,0,-1,0,-1,1,1,-1};
                                                
    class pa3{
        public:
        int x;
        int y,z;
        pa3(int x=0,int y=0,int z=0):x(x),y(y),z(z) {}
        bool operator < (const pa3 &p) const{
            if(x!=p.x) return x<p.x;
            if(y!=p.y) return y<p.y;
             return z<p.z;
            //return x != p.x ? x<p.x: y<p.y;
        }
        bool operator > (const pa3 &p) const{
            if(x!=p.x) return x>p.x;
            if(y!=p.y) return y>p.y;
             return z>p.z;
            //return x != p.x ? x<p.x: y<p.y;
        }
        bool operator == (const pa3 &p) const{
            return x==p.x && y==p.y && z==p.z;
        }
            bool operator != (const pa3 &p) const{
                return !( x==p.x && y==p.y && z==p.z);
        }
     
    };
     
    class pa4{
        public:
        int x;
        int y,z,w;
        pa4(int x=0,int y=0,int z=0,int w=0):x(x),y(y),z(z),w(w) {}
        bool operator < (const pa4 &p) const{
            if(x!=p.x) return x<p.x;
            if(y!=p.y) return y<p.y;
            if(z!=p.z)return z<p.z;
            return w<p.w;
            //return x != p.x ? x<p.x: y<p.y;
        }
        bool operator > (const pa4 &p) const{
            if(x!=p.x) return x>p.x;
            if(y!=p.y) return y>p.y;
            if(z!=p.z)return z>p.z;
            return w>p.w;
            //return x != p.x ? x<p.x: y<p.y;
        }
        bool operator == (const pa4 &p) const{
            return x==p.x && y==p.y && z==p.z &&w==p.w;
        }
            
     
    };
    class pa2{
        public:
        int x,y;
        pa2(int x=0,int y=0):x(x),y(y) {}
        pa2 operator + (pa2 p) {return pa2(x+p.x,y+p.y);}
        pa2 operator - (pa2 p) {return pa2(x-p.x,y-p.y);}
        bool operator < (const pa2 &p) const{
            return y != p.y ? y<p.y: x<p.x;
        }
        bool operator > (const pa2 &p) const{
            return x != p.x ? x<p.x: y<p.y;
        }
        bool operator == (const pa2 &p) const{
            return abs(x-p.x)==0 && abs(y-p.y)==0;
        }
        bool operator != (const pa2 &p) const{
            return !(abs(x-p.x)==0 && abs(y-p.y)==0);
        }
            
     
    };
     
     
     
    string itos( int i ) {
        ostringstream s ;
        s << i ;
        return s.str() ;
    }
     
    int Gcd(int v,int b){
        if(v==0) return b;
        if(b==0) return v;
        if(v>b) return Gcd(b,v);
        if(v==b) return b;
        if(b%v==0) return v;
        return Gcd(v,b%v);
    }
     
     
     
    int extgcd(int a, int b, int &x, int &y) {
        if (b == 0) {
            x = 1;
            y = 0;
            return a;
        }
        int d = extgcd(b, a%b, y, x);
        y -= a/b * x;
        return d;
    }
    pa operator+(const pa & l,const pa & r) {   
        return {l.first+r.first,l.second+r.second};                                    
    }    
    pa operator-(const pa & l,const pa & r) {   
        return {l.first-r.first,l.second-r.second};                                    
    }  
     
     
    pair<double,double> operator-(const pair<double,double> & l,const pair<double,double> & r) {   
        return {l.first-r.first,l.second-r.second};                                    
    }  
     
    ostream& operator<<(ostream& os, const vector<int>& VEC){
        for(auto v:VEC)os<<v<<" ";
        return os;
    }
     
     ostream& operator<<(ostream& os, const pair<double,double>& PAI){
        os<<PAI.first<<" : "<<PAI.second;
        return os;
    }
     
     
    ostream& operator<<(ostream& os, const pa& PAI){
        os<<PAI.first<<" : "<<PAI.second;
        return os;
    }
     
    ostream& operator<<(ostream& os, const pa3& PAI){
        os<<PAI.x<<" : "<<PAI.y<<" : "<<PAI.z;
        return os;
    }
     
    ostream& operator<<(ostream& os, const pa4& PAI){
        os<<PAI.x<<" : "<<PAI.y<<" : "<<PAI.z<<" : "<<PAI.w;
        return os;
    }
     
    ostream& operator<<(ostream& os, const vector<pa>& VEC){
        for(auto v:VEC)os<<v<<" ";
        return os;
    }
     
     
    ostream& operator<<(ostream& os, const vector<pa3>& VEC){
        for(auto v:VEC){
            os<<v<<" ";
        os<<endl;
        }
        return os;
    }
     
    int beki(int wa,ll rr,int warukazu){
        if(rr==0) return 1%warukazu;
        if(rr==1) return wa%warukazu;
        wa%=warukazu;
        if(rr%2==1) return ((ll)beki(wa,rr-1,warukazu)*(ll)wa)%warukazu;
        ll zx=beki(wa,rr/2,warukazu);
        return (zx*zx)%warukazu;
    }
     
     
                  
    int pr[2500002];
    int inv[2500002];
     
     
     
     
   const int mod=998244353;
    int comb(int nn,int rr){
        if(nn==-1&&rr==-1)return 1;
        if(rr<0 || rr>nn || nn<0) return 0;
        int r=pr[nn]*inv[rr];
        r%=mod;
        r*=inv[nn-rr];
        r%=mod;
        return r;
    }
     
    void gya(int ert){
        pr[0]=1;
        for(int i=1;i<=ert;i++){
            pr[i]=((ll)pr[i-1]*i)%mod;
        }
            inv[ert]=beki(pr[ert],mod-2,mod);
        for(int i=ert-1;i>=0;i--){
            inv[i]=(ll)inv[i+1]*(i+1)%mod;
        }
    }
     
     
    int beki(int a,int b){
        int ANS=1;
        int be=a%mod;
        while(b){
            if(b&1){
                ANS*=be;
                ANS%=mod;
            }
            be*=be;
            be%=mod;
            b/=2;
        }
        return ANS;
    }
     
                    
     
     
                    
                  //   cin.tie(0);
                //  ios::sync_with_stdio(false);
                    //priority_queue<pa3,vector<pa3>,greater<pa3>> pq;            
                     //sort(ve.begin(),ve.end(),greater<int>());
    //    mt19937(clock_per_sec);
      //  mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()) ;
     // a,b,c : positive int   a*b<=c  <=>  a<=c/b
    //  auto dfs=[&](auto &&self,int r,int p)->int{
    //  };
    class Point{
        public:
        double x,y;
        Point(double x=0,double y=0):x(x),y(y) {}
        Point operator + (Point p) {return Point(x+p.x,y+p.y);}
        Point operator - (Point p) {return Point(x-p.x,y-p.y);}
        Point operator * (double a) {return Point(x*a,y*a);}
        Point operator / (double a) {return Point(x/a,y/a);}
        double absv() {return sqrt(norm());}
        double norm() {return x*x+y*y;}
        bool operator < (const Point &p) const{
            return x != p.x ? x<p.x: y<p.y;
        }
        bool operator == (const Point &p) const{
            return fabs(x-p.x)<EPS && fabs(y-p.y)<EPS;
        }
    };
     
    class Line{
        public:
        // y=ax+b
        double a;
        double b;
        Line(double a=0,double b=0):a(a),b(b) {}
        
        double eval(double x){return a*x+b;}
        bool operator < (const Line &p) const{
            return abs(a-p.a)>EPS ? a<p.a: b<p.b;
        }
        
    };
     
    Point intersect_line(Line A,Line B){
        double x=(B.b-A.b)/(A.a-B.a);
        return Point(x,A.eval(x));
    }
     
    Line line_from_2_Point(Point A,Point B){
        // line which through A,B
        double a=(B.y-A.y)/(B.x-A.x);
        return Line(a,A.y-a*A.x);
    }
     
struct unionfind{
    private:
    public:
    
vector<int> par,ranks,kosuu;
    
    void shoki(int N){
        par.resize(N+1,0);
        ranks.resize(N+1,0);
        kosuu.resize(N+1,1);
        for(int i=0;i<=N;i++){
            par[i]=i;
        }
    }
    int root(int x){
        return par[x]==x ? x : par[x]=root(par[x]);
    }
    bool same(int x,int y){
        return root(x)==root(y);
    }
    bool is_root(int x){
        return x==root(x);
    }
    void unite(int x,int y){
        x=root(x);
        y=root(y);
        int xx=kosuu[x],yy=kosuu[y];
        if(x==y) return;
        if(ranks[x]<ranks[y]){
            par[x]=y;
            kosuu[y]=yy+xx;
        }
        else {
            par[y]=x;
            if(ranks[x]==ranks[y]) ranks[x]=ranks[x]+1;
            kosuu[x]=yy+xx;
        }
        return;
    }
};
struct segsum{
    //       1
    //   2        3
    // 4   5   6    7
    
    
    private:
    public:
    
    // 1<<15 = 32768
    // 1<<16 = 65536
    // 1<<17 = 131072
    // 1<<18 = 262144
    
    int cor=(1<<19);
    
    vector<int> vec;
    
    void shoki1(){
        vec.resize(2*cor+3, 0);
    }
    void shoki2(){
        for(int i=cor-1;i>0;i--) vec[i]=vec[2*i]+vec[2*i+1];
    }
    void clear(){    
        for(int i=0;i<(int)vec.size();i++)vec[i]=0;
    }
    
    void updadd(int x,int w){
        //x 項目に w加算
        x+=cor;
        vec[x]+=w;
        x/=2;
        while(x){
            vec[x]=vec[2*x]+vec[2*x+1];
            x/=2;
        }
    }
    
    void updchan(int x,int w){
        //x項目をwに変更
        x+=cor;
        vec[x]=w;
        while(x){
            x/=2;
            vec[x]=vec[2*x]+vec[2*x+1];
        }       
    }
    
    // [a,b)
    int sum(int a,int b){
        int hi=0,mi=0;
        a+=cor,b+=cor;
        while(a<b){
            if(a&1){
                hi=hi+vec[a];
                a++;
            }
            if(b&1){
                b--;
                mi=vec[b]+mi;
            }
            a/=2,b/=2;
        }
        return hi+mi;
    }
    
    // 位置pからはじめて和がx以上になる位置．ない場合はcorが返る
    int lower_bound(int p,int x){
        p+=cor;
        int ima=0;
        while(1){
            while(!(p&1))p/=2;
            if(ima+vec[p]>=x)break;//条件を満たさなくなる
            ima=ima+vec[p];
            p++;
            if(p==(p&(-p))) return cor;
        }
        while(1){
            if(p>=cor) return p-cor;
            p*=2;
            if(ima+vec[p]<x){//条件を満たす
                ima+=vec[p];
                p++;
            }
        }
    }
    
    // 位置pからはじめて和がxより大になる位置．ない場合はcorが返る
    int upper_bound(int p,int x){
        p+=cor;
        int ima=0;
        while(1){
            while(!(p&1))p/=2;
            if(ima+vec[p]>x)break;//条件を満たさなくなる
            ima=ima+vec[p];
            p++;
            if(p==(p&(-p))) return cor;
        }
        while(1){
            if(p>=cor) return p-cor;
            p*=2;
            if(ima+vec[p]<=x){//条件を満たす
                ima+=vec[p];
                p++;
            }
        }
    }   
    
};
void solve(){
    int n,q;
    cin>>n>>q;
    string s;
    cin>>s;
    vector<int>ve;
    for(auto c:s){
        if(c=='(')ve.pb(0);
        else ve.pb(1);
    }
    segsum ss;
    ss.shoki1();
    for(int i=0;i<n-1;i++)if(ve[i]!=ve[i+1])ss.vec[ss.cor+i]=1;
    ss.shoki2();
    
    while(q--){
        int t;
        cin>>t;
        if(t==1){
            int y;
            cin>>y;
            y--;
            ve[y]=1-ve[y];
            if(y)ss.updchan(y-1,1-ss.sum(y-1,y));
            if(y<n-1)ss.updchan(y,1-ss.sum(y,y+1));
            
        }
        else{
            int l,r;
            cin>>l>>r;
            l--;
            int sum=ss.sum(l,r-1);
            if(ve[l]==0)sum++;
            if(ve[r-1]==1)sum++;
            cout<<sum/2<<endl;
        }
    }
    
}
  
    
    signed main(){
     
        //mod=inf;
        cin.tie(0);
        ios::sync_with_stdio(false);
        int n=1;
        //cin>>n;
        for(int i=0;i<n;i++)solve();
     
        return 0;
        
    }
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0