Advertisement
jeff69

Untitled

Mar 29th, 2017
64
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.02 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. const int MX=1e6+4;
  5. #define left ghfghgf
  6. #define right ghfghfgh
  7. int n,ar[MX];
  8. struct Node
  9. {
  10.     int fours,sevens,opt47,opt74,lasy;
  11.     Node()
  12.     {
  13.         lasy=fours=sevens=opt47=opt74=0;
  14.     }
  15. }tree[4*MX];
  16. Node merge(Node left,Node right)
  17. {
  18.     Node B;
  19.     int z=left.fours+right.fours,y=left.sevens+right.sevens;
  20.     z=max(z,y);
  21.     B.opt47=max(left.opt47+right.sevens,left.fours+right.opt47);
  22.     B.opt47=max(left.fours+right.sevens,B.opt47);
  23.     B.opt74=max(left.opt74+right.fours,left.sevens+right.opt74);
  24.     B.opt74=max(B.opt74,left.sevens+right.fours);
  25.     B.sevens=right.sevens+left.sevens;
  26.     B.fours=right.fours+left.fours;
  27.     B.opt47=max(B.opt47,z);
  28.     B.opt74=max(B.opt74,z);
  29.     return B;
  30. }
  31. int st,en,IN;
  32. void build(int x=1,int l=1,int r=n)
  33. {
  34.     if(l==r)
  35.     {
  36.         tree[x].fours=(ar[l]==4);
  37.         tree[x].sevens=(ar[l]==7);
  38.         tree[x].opt47=1;
  39.         tree[x].opt74=1;
  40.         return;
  41.     }
  42.     build(2*x,l,(l+r)/2);
  43.     build(2*x+1,(l+r)/2+1,r);
  44.     tree[x]=merge(tree[x*2],tree[2*x+1]);
  45. }
  46. void Switch(Node& S,int lz)
  47. {
  48.     S.lasy++;
  49.     if((lz)%2)return;
  50.     swap(S.fours,S.sevens);
  51.     swap(S.opt47,S.opt74);
  52. }
  53. void update(int x=1,int l=1,int r=n,int lz=0)
  54. {
  55.     if(r<st||en<l)
  56.         return Switch(tree[x],lz+1);
  57.     if(st<=l&&r<=en)
  58.        return Switch(tree[x],lz);
  59.     update(2*x,l,(l+r)/2,lz+tree[x].lasy);
  60.     update(2*x+1,(l+r)/2+1,r,lz+tree[x].lasy);
  61.    // cout<<l<<' '<<r<<' '<<tree[x].opt74<<endl;
  62.     tree[x]=merge(tree[x*2],tree[2*x+1]);
  63. }
  64. int m;
  65. char bb[MX];
  66. int main()
  67. {
  68.     cin>>n>>m;
  69.     scanf("%s",bb);
  70.     for(int i=0;i<n;i++)
  71.         ar[i+1]=bb[i]-'0';
  72.     build();
  73.     for(int i=1;i<=m;i++)
  74.     {
  75.         char cc[22];
  76.         scanf(" %s",cc);
  77.         string h=cc;
  78.         if(h=="switch")
  79.         {
  80.             scanf("%d%d",&st,&en);
  81.             update();
  82.         }
  83.         else
  84.             printf("%d %d\n",tree[1].opt47,tree[1].opt74);
  85.     }
  86.     return 0;
  87. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement