API tools faq
paste
Advertisement
ekzolot

Untitled

ekzolot
May 4th, 2024
734
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 9.85 KB | None | 0 0
raw download clone embed print report
  1. //A
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4. struct Note{
  5.     int l;
  6.     int r;
  7.     int ans;
  8.     int d=0;
  9. };
  10. void build(vector<Note>& tree, vector<int>& a, int L, int R, int i){
  11.     tree[i].l=L;
  12.     tree[i].r=R;
  13.     if (R-L==1){
  14.         tree[i].ans=a[L];
  15.         return;
  16.     }
  17.     int M=(R+L)/2;
  18.     build(tree, a, L, M, 2*i+1);
  19.     build(tree, a, M, R, 2*i+2);
  20.     tree[i].ans=max(tree[2*i+1].ans, tree[2*i+2].ans);
  21. }
  22. void push(vector<Note>& tree, int i){
  23.     tree[2*i+1].d+=tree[i].d;
  24.     tree[2*i+2].d+=tree[i].d;
  25.     tree[i].d=0;
  26. }
  27. void change(vector<Note>& tree, int i, int x, int L, int R){
  28.     if (tree[i].l>=R || tree[i].r<=L){
  29.         return;
  30.     }
  31.     if(tree[i].l>=L && tree[i].r<=R){
  32.         tree[i].d+=x;
  33.         return;
  34.     }
  35.     push(tree, i);
  36.     change(tree, 2*i+1, x, L, R);
  37.     change(tree, 2*i+2, x, L, R);
  38.     tree[i].ans=max(tree[2*i+1].ans+tree[2*i+1].d, tree[2*i+2].ans+tree[2*i+2].d);
  39. }
  40. int answer(vector<Note>& tree, int i, int L, int R){
  41.     if (tree[i].l>=R || tree[i].r<=L){
  42.         return -1;
  43.     }
  44.     if(tree[i].l>=L && tree[i].r<=R){
  45.         return tree[i].ans+tree[i].d;
  46.     }
  47.     push(tree, i);
  48.     int m1=answer(tree, 2*i+1, L, R);
  49.     int m2=answer(tree, 2*i+2, L, R);
  50.     tree[i].ans=max(tree[2*i+1].ans+tree[2*i+1].d, tree[2*i+2].ans+tree[2*i+2].d);
  51.     return max(m1, m2);
  52. }
  53. int main(){
  54.     int n;
  55.     cin>>n;
  56.     vector<int> a(n);
  57.     for (int i=0; i<n; i++){
  58.         cin>>a[i];
  59.     }
  60.     vector<Note> tree(4*n);
  61.     build(tree, a, 0, n, 0);
  62.     int M;
  63.     cin>>M;
  64.     for (int i=0; i<M; i++){
  65.         char x;
  66.         cin>>x;
  67.         if (x=='a'){
  68.             int L, R, add;
  69.             cin>>L>>R>>add;
  70.             L--;
  71.             change(tree, 0, add, L, R);
  72.         }else{
  73.             int L, R;
  74.             cin>>L>>R;
  75.             L--;
  76.             cout<<answer(tree, 0, L, R)<<" ";
  77.         }
  78.     }
  79.     return 0;
  80. }
  81.  
  82.  
  83. //B
  84. #include <bits/stdc++.h>
  85. #define int long long
  86. using namespace std;
  87. struct Note{
  88.     int pref;
  89.     int suf;
  90.     int ans;
  91. };
  92. void build(vector<Note>& tree, vector<int>& a, int v, int l, int r){
  93.     if (r-l==1){
  94.         if (a[l]==0){
  95.             tree[v].pref=1;
  96.             tree[v].suf=1;
  97.             tree[v].ans=1;
  98.         }else{
  99.             tree[v].pref=0;
  100.             tree[v].suf=0;
  101.             tree[v].ans=0;
  102.         }
  103.         return;
  104.     }
  105.     int m=(l+r)/2;
  106.     build(tree, a, 2*v+1, l, m);
  107.     build(tree, a, 2*v+2, m, r);
  108.     tree[v].ans=tree[2*v+1].suf+tree[2*v+2].pref;
  109.     tree[v].ans=max(tree[v].ans, tree[2*v+1].ans);
  110.     tree[v].ans=max(tree[v].ans, tree[2*v+2].ans);
  111.     if (tree[2*v+2].ans==r-m){
  112.         tree[v].suf=tree[2*v+1].suf+r-m;
  113.     }else{
  114.         tree[v].suf=tree[2*v+2].suf;
  115.     }
  116.     if (tree[2*v+1].ans==m-l) {
  117.         tree[v].pref = m - l + tree[2 * v + 2].pref;
  118.     }else{
  119.         tree[v].pref=tree[2*v+1].pref;
  120.     }
  121. }
  122. void change(vector<Note>& tree, vector<int>& a, int v, int l, int r, int pos, int x){
  123.     if (r-l==1){
  124.         if (x==0){
  125.             tree[v].pref=1;
  126.             tree[v].suf=1;
  127.             tree[v].ans=1;
  128.         }else{
  129.             tree[v].pref=0;
  130.             tree[v].suf=0;
  131.             tree[v].ans=0;
  132.         }
  133.         return;
  134.     }
  135.     int m=(r+l)/2;
  136.     if (pos<m){
  137.         change(tree, a, 2*v+1, l, m, pos, x);
  138.     }else{
  139.         change(tree, a, 2*v+2, m,r, pos, x);
  140.     }
  141.     tree[v].ans=tree[2*v+1].suf+tree[2*v+2].pref;
  142.     tree[v].ans=max(tree[v].ans, tree[2*v+1].ans);
  143.     tree[v].ans=max(tree[v].ans, tree[2*v+2].ans);
  144.     if (tree[2*v+2].ans==r-m){
  145.         tree[v].suf=tree[2*v+1].suf+r-m;
  146.     }else{
  147.         tree[v].suf=tree[2*v+2].suf;
  148.     }
  149.     if (tree[2*v+1].ans==m-l) {
  150.         tree[v].pref = m - l + tree[2 * v + 2].pref;
  151.     }else{
  152.         tree[v].pref=tree[2*v+1].pref;
  153.     }
  154. }
  155. int ans(vector<Note>& tree, vector<int>& a, int v, int l, int r, int L, int R){
  156.     if (L>=r || R<=l){
  157.         return 0;
  158.     }
  159.     if (L<=l && R>=r){
  160.         //cout<<l<<" "<<r<<" "<<L<<" "<<R<<" "<<tree[v].ans<<"\n";
  161.         return tree[v].ans;
  162.     }
  163.     int m=(r+l)/2;
  164.     if (L<=m && R<=m){
  165.         return ans(tree, a, 2*v+1, l, m, L, R);
  166.     }
  167.     if (L>=m && R>=m){
  168.         return ans(tree, a, 2*v+2, m, r, L, R);
  169.     }
  170.     //cout<<l<<" "<<r<<" "<<L<<" "<<R<<" "<<min(m-L, tree[2*v+1].suf)+min(R-m, tree[2*v+2].pref)<<"\n";
  171.     int y=min(m-L, tree[2*v+1].suf)+min(R-m, tree[2*v+2].pref);
  172.     y=max(y, ans(tree, a, 2*v+1, l, m, L, R));
  173.     y=max(y, ans(tree, a, 2*v+2, m, r, L, R));
  174.     return y;
  175. }
  176. signed main(){
  177.     int N;
  178.     cin>>N;
  179.     if (N<10000){
  180.         vector<int> q(N);
  181.         for (int i=0; i<N; i++){
  182.             cin>>q[i];
  183.         }
  184.         int m;
  185.         cin>>m;
  186.         while(m--){
  187.             char type;
  188.             cin>>type;
  189.             if (type=='+'){
  190.                 int L, R, d;
  191.                 cin>>L>>R>>d;
  192.                 L--;
  193.                 for (int i=L; i<R; i++){
  194.                     q[i]+=d;
  195.                 }
  196.             }else{
  197.                 int L, R;
  198.                 cin>>L>>R;
  199.                 L--;
  200.                 int ans=0;
  201.                 int cnt=0;
  202.                 for (int i=L; i<R-1; i++){
  203.                     if (q[i+1]-q[i]!=1){
  204.                         cnt=0;
  205.                     }else{
  206.                         cnt++;
  207.                     }
  208.                     ans=max(ans, cnt);
  209.                 }
  210.                 cout<<ans+1<<"\n";
  211.             }
  212.         }
  213.         return 0;
  214.     }
  215.     vector<int> b(N);
  216.     for (int i=0; i<N; i++) {
  217.         cin>>b[i];
  218.     }
  219.     int n=N-1;
  220.     vector<int> a(n);
  221.     for (int i=0; i<n; i++){
  222.         a[i]=b[i+1]-b[i]-1;
  223.     }
  224.     vector<Note> tree(4*n);
  225.     build(tree, a, 0, 0, n);
  226.     int m;
  227.     cin>>m;
  228.     while(m--){
  229.         char type;
  230.         cin>>type;
  231.         if (type=='+'){
  232.             int L, R, d;
  233.             cin>>L>>R>>d;
  234.             L--;
  235.             if (L-1>=0 && L-1<n){
  236.                 a[L-1]+=d;
  237.                 change(tree, a, 0, 0, n, L-1, a[L-1]);
  238.             }
  239.             if (R-1<n && R-1>=0){
  240.                 a[R-1]-=d;
  241.                 change(tree, a, 0, 0, n, R-1, a[R-1]);
  242.             }
  243.         }
  244.         else{
  245.             int L, R;
  246.             cin>>L>>R;
  247.             L--;
  248.             if (L==n || L==R-1){
  249.                 cout<<1<<"\n";
  250.                 continue;
  251.             }
  252.             cout<<ans(tree, a, 0, 0, n, L, R-1)+1<<"\n";
  253.         }
  254.     }
  255.     return 0;
  256. }
  257.  
  258.  
  259. //C
  260. #include <bits/stdc++.h>
  261. #define int long long
  262. using namespace std;
  263. struct Note{
  264.     vector<int> v;
  265.     int l;
  266.     int r;
  267.     int d=0;
  268. };
  269. vector<int> binary_rep(int x){
  270.     vector<int> ans;
  271.     while(x>0){
  272.         ans.push_back(x%2);
  273.         x/=2;
  274.     }
  275.     while(ans.size()<40){
  276.         ans.push_back(0);
  277.     }
  278.     reverse(ans.begin(), ans.end());
  279.     return ans;
  280. }
  281. void unite(vector<int>& vert, vector<int>& left, vector<int>& right){
  282.     for (int i=0; i<40; i++){
  283.         vert[i]=left[i]+right[i];
  284.     }
  285. }
  286. void build(vector<Note>& tree, int idx, int L, int R, vector<vector<int>>& a){
  287.     (tree[idx].v).resize(40);
  288.     tree[idx].l=L;
  289.     tree[idx].r=R;
  290.     if (R-L==1){
  291.         tree[idx].v=a[L];
  292.         return;
  293.     }
  294.     int M=(L+R)/2;
  295.     build(tree, 2*idx+1, L, M, a);
  296.     build(tree, 2*idx+2, M, R, a);
  297.     unite(tree[idx].v, tree[2*idx+1].v, tree[2*idx+2].v);
  298. }
  299. void push(vector<Note>& tree, int idx){
  300.     tree[2*idx+1].d=tree[idx].d^tree[2*idx+1].d;
  301.     tree[2*idx+2].d=tree[idx].d^tree[2*idx+2].d;
  302.     tree[idx].d=0;
  303. }
  304. vector<int> counting_vector(vector<int>& ans, int x, int k){
  305.     vector<int> cnt(40);
  306.     for (int i=0; i<40; i++){
  307.         if (!((x>>(39-i))&1)){
  308.             cnt[i]=ans[i];
  309.         }else{
  310.             cnt[i]=k-ans[i];
  311.         }
  312.     }
  313.     return cnt;
  314. }
  315. void change(vector<Note>& tree, int idx, int L, int R, int x){
  316.     if (tree[idx].l>=R || tree[idx].r<=L){
  317.         return;
  318.     }
  319.     if (L<=tree[idx].l && R>=tree[idx].r){
  320.         tree[idx].d=tree[idx].d^x;
  321.         return;
  322.     }
  323.     push(tree, idx);
  324.     change(tree, 2*idx+1, L, R, x);
  325.     change(tree, 2*idx+2, L, R, x);
  326.     int len1=tree[2*idx+1].r-tree[2*idx+1].l;
  327.     int len2=tree[2*idx+2].r-tree[2*idx+2].l;
  328.     vector<int> y1=counting_vector(tree[2*idx+1].v, tree[2*idx+1].d, len1);
  329.     vector<int> y2=counting_vector(tree[2*idx+2].v, tree[2*idx+2].d, len2);
  330.     unite(tree[idx].v, y1, y2);
  331. }
  332. int counting(vector<int>& ans, int x, int k){
  333.     int cnt=0;
  334.     for (int i=0; i<40; i++){
  335.         if (!((x>>(39-i))&1)){
  336.             cnt+=ans[i]*(1<<(39-i));
  337.         }else{
  338.             cnt+=(1<<(39-i))*(k-ans[i]);
  339.         }
  340.     }
  341.     return cnt;
  342. }
  343. int answer(vector<Note>& tree, int idx, int L, int R){
  344.     if (L>=tree[idx].r || R<=tree[idx].l){
  345.         return 0;
  346.     }
  347.     if (L<=tree[idx].l && R>=tree[idx].r){
  348.         int len=tree[idx].r-tree[idx].l;
  349.         return counting(tree[idx].v, tree[idx].d, len);
  350.     }
  351.     push(tree, idx);
  352.     int len1=tree[2*idx+1].r-tree[2*idx+1].l;
  353.     int len2=tree[2*idx+2].r-tree[2*idx+2].l;
  354.     vector<int> y1=counting_vector(tree[2*idx+1].v, tree[2*idx+1].d, len1);
  355.     vector<int> y2=counting_vector(tree[2*idx+2].v, tree[2*idx+2].d, len2);
  356.     unite(tree[idx].v, y1, y2);
  357.     return answer(tree, 2*idx+1, L, R)+answer(tree, 2*idx+2, L, R);
  358. }
  359. signed main(){
  360.     ios::sync_with_stdio(0);
  361.     cin.tie(0);
  362.     cout.tie(0);
  363.     int n;
  364.     cin>>n;
  365.     vector<vector<int>> a(n);
  366.     for (int i=0; i<n; i++){
  367.         int q;
  368.         cin>>q;
  369.         a[i]=binary_rep(q);
  370.     }
  371.     int m;
  372.     cin>>m;
  373.     vector<Note> tree(4*n);
  374.     build(tree, 0, 0, n, a);
  375.     while(m--){
  376.         int t;
  377.         cin>>t;
  378.         if (t==1){
  379.             int L, R;
  380.             cin>>L>>R;
  381.             L--;
  382.             cout<<answer(tree, 0, L, R)<<"\n";
  383.         }
  384.         else{
  385.             int L, R, x;
  386.             cin>>L>>R>>x;
  387.             L--;
  388.             change(tree, 0, L, R, x);
  389.         }
  390.     }
  391.     return 0;
  392. }
  393.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!