YEZAELP

o20_oct_dvd

Jan 9th, 2022 (edited)
655
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. const int N = 1e5 + 10;
  5. using lli = long long;
  6. const lli PB = 98765431;
  7. lli fw[N], qs[N], hsh[N];
  8. int ar[N];
  9. int n;
  10.  
  11. lli Sum(int pst, lli sum = 0){
  12.     for(int i=pst;i>=1;i-=i&-i)
  13.         sum += fw[i];
  14.     return sum;
  15. }
  16.  
  17. void Update(int pst, lli val){
  18.     for(int i=pst;i<=n;i+=i&-i)
  19.         fw[i] += val;
  20. }
  21.  
  22. lli RangeSum(int s, int e){
  23.     return Sum(e) - Sum(s - 1);
  24. }
  25.  
  26. int main(){
  27.  
  28.     int k;
  29.     scanf("%d %d", &n, &k);
  30.  
  31.     lli p = 1;
  32.     for(int i=1;i<=n;i++){
  33.         p = p * PB;
  34.         hsh[i] = i * p;
  35.         qs[i] = qs[i - 1] + hsh[i];
  36.         Update(i, hsh[i]);
  37.     }
  38.  
  39.     for(int i=1;i<=k;i++){
  40.         int opr, s, e;
  41.         scanf("%d %d %d", &opr, &s, &e);
  42.         s ++, e ++;
  43.         if(opr == 0){
  44.             lli curs = RangeSum(s, s);
  45.             lli cure = RangeSum(e, e);
  46.             Update(s, -curs);
  47.             Update(e, -cure);
  48.             Update(e, curs);
  49.             Update(s, cure);
  50.         }
  51.         else if(opr == 1){
  52.             if(qs[e] - qs[s - 1] == RangeSum(s, e)) printf("YES\n");
  53.             else printf("NO\n");
  54.         }
  55.     }
  56.  
  57.     return 0;
  58. }
RAW Paste Data Copied