Advertisement
TheAnshul

Untitled

Jun 27th, 2018
182
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.21 KB | None | 0 0
  1.  /***************************************************************************
  2.   * #######                    #                                            *
  3.   *    #     #    #  ######   # #    #    #   ####   #    #  #    #  #      *
  4.   *    #     #    #  #       #   #   ##   #  #       #    #  #    #  #      *
  5.   *    #     ######  #####  #     #  # #  #   ####   ######  #    #  #      *
  6.   *    #     #    #  #      #######  #  # #       #  #    #  #    #  #      *
  7.   *    #     #    #  #      #     #  #   ##  #    #  #    #  #    #  #      *
  8.   *    #     #    #  ###### #     #  #    #   ####   #    #   ####   ###### *
  9.   ***************************************************************************/
  10.  #include<bits/stdc++.h>
  11.  #define ll          long long
  12.  #define pb          push_back
  13.  #define    endl        '\n'
  14.  #define pii         pair<ll int,ll int>
  15.  #define vi          vector<ll int>
  16.  #define all(a)      (a).begin(),(a).end()
  17.  #define F           first
  18.  #define S           second
  19.  #define sz(x)       (ll int)x.size()
  20.  #define hell        1000000007
  21.  #define rep(i,a,b) for(ll int i=a;i<b;i++)
  22.  #define lbnd        lower_bound
  23.  #define ubnd        upper_bound
  24.  #define bs          binary_search
  25.  #define mp          make_pair
  26.  using namespace std;
  27.  
  28.  #define N  2000005
  29.  ll tree[5*N];
  30.  bool lazy[5*N];
  31.  bool a[N];
  32.  void build(ll node,ll start,ll end)
  33.  {
  34.     if(start==end)
  35.     {
  36.         tree[node]=a[start];
  37.         return;
  38.     }
  39.     ll mid = (start+end)/2;
  40.     build(2*node,start,mid);
  41.     build(2*node+1,mid+1,end);
  42.     tree[node]=tree[2*node]+tree[2*node+1];
  43.     return;
  44.  }
  45.  void update(ll node,ll start,ll end,ll l,ll r)
  46.  {
  47.     if(start>end || l>r || l>end || r<start)
  48.         return;
  49.     if(lazy[node])
  50.     {
  51.         tree[node]=(end-start+1)-tree[node];
  52.         if(start!=end)
  53.         {
  54.             lazy[2*node]=1;
  55.             lazy[2*node+1]=1;
  56.         }
  57.         lazy[node]=0;
  58.     }
  59.     if(l<=start && r>=end)
  60.     {
  61.         tree[node]=(end-start+1)-tree[node];
  62.         if(start!=end)
  63.         {
  64.             lazy[2*node]=1;
  65.             lazy[2*node+1]=1;
  66.         }
  67.         lazy[node]=0;
  68.         return;
  69.     }
  70.     ll mid=(start+end)/2;
  71.     update(2*node,start,mid,l,r);
  72.     update(2*node+1,mid+1,end,l,r);
  73.     tree[node]=tree[2*node]+tree[2*node+1];
  74.     return;
  75.  }
  76.  ll query(ll node,ll start,ll end,ll l,ll r)
  77.  {
  78.     if(start>end || l>r || l>end || r<start)
  79.         return 0;
  80.     if(lazy[node])
  81.     {
  82.         tree[node]=(end-start+1)-tree[node];
  83.         if(start!=end)
  84.         {
  85.             lazy[2*node]=1;
  86.             lazy[2*node+1]=1;
  87.         }
  88.         lazy[node]=0;
  89.     }
  90.     if(l<=start && r>=end)
  91.     {
  92.         return tree[node];
  93.     }
  94.     ll mid=(start+end)/2;
  95.     ll p=query(2*node,start,mid,l,r);
  96.     p+=query(2*node+1,mid+1,end,l,r);
  97.     return p;
  98.  }
  99.  int main()
  100.  {
  101.     ios_base::sync_with_stdio(false);
  102.     cin.tie(0);
  103.     cout.tie(0);
  104.     int TESTS=1;
  105.  // cin>>TESTS;
  106.     while(TESTS--)
  107.     {
  108.         ll n,m;
  109.         cin>>n>>m;
  110.         string s;
  111.         cin>>s;
  112.         rep(i,1,n)
  113.         {
  114.             if(s[i-1]=='>')
  115.                 a[i]=0;
  116.             else
  117.                 a[i]=1;
  118.         }
  119.         ll t,x,y;
  120.         n--;
  121.         build(1,1,n);
  122.         // rep(i,1,n+1)
  123.         // cout<<a[i]<<" ";
  124.         // cout<<endl;
  125.         // rep(i,1,4*n)
  126.         // cout<<tree[i]<<" ";
  127.         // cout<<endl;
  128.         rep(i,0,m)
  129.         {
  130.             cin>>t>>x>>y;
  131.             if(t==1)
  132.             {
  133.                 // if(x==y)
  134.                 //  cout<<"fuck";
  135.                 update(1,1,n,x,y-1);
  136.             }
  137.             else
  138.             {
  139.                 if(y>x)
  140.                     cout<<query(1,1,n,x,y-1)<<endl;
  141.                 else
  142.                     cout<<((x-y)-query(1,1,n,y,x-1))<<endl;
  143.                 // if(x==y)
  144.                 //  cout<<"fuck";
  145.             }
  146.         }
  147.     }
  148.     return 0;
  149.  }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement