daily pastebin goal
18%
SHARE
TWEET

Untitled

a guest Jun 19th, 2017 46 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. #define f first
  3. #define s second
  4. #define mp make_pair
  5. #define pb push_back
  6. #define lp(i,a,n) for(int i=(a);i<=(int)(n);++i)
  7. #define lpd(i,a,n) for(int i=(a);i>=(int)(n);--i)
  8. #define mem(a,b) memset(a,b,sizeof a)
  9. #define all(v) v.begin(),v.end()
  10. #define println(a) cout <<(a) <<endl
  11. #define sz(x) ((int)(x).size())
  12. #define readi(x) scanf("%d",&x)
  13. #define read2i(x,y) scanf("%d%d",&x,&y)
  14. #define read3i(x,y,z) scanf("%d%d%d",&x,&y,&z)
  15. #define readll(x) scanf("%I64d",&x)
  16. #define mod 1000000007
  17. #define eps 1e-6
  18. #define infi 1000000000
  19. #define infll 1000000000000000000ll
  20. using namespace std;
  21. typedef long long ll;
  22. typedef pair<int, int> pii;
  23. typedef pair<ll, ll> pll;
  24. typedef vector<int> vi;
  25. typedef vector<vi> vvi;
  26. typedef vector<ll> vll;
  27. typedef set<int> si;
  28. typedef map<int,int> mii;
  29.  
  30. const int N = 100002;
  31. int n,q,a[N];
  32. ll tree[N],prodTreeL[N],prodTreeR[N];
  33.  
  34. void update(int i, ll diff, ll tree[]){
  35.   while (i < N){
  36.     tree[i] += diff;
  37.     i += i & -i;
  38.   }
  39. }
  40.  
  41. ll query(int i, ll tree[]){
  42.   ll sum = 0;
  43.   while(i > 0){
  44.     sum += tree[i];
  45.     i -= i & -i;
  46.   }
  47.   return sum;
  48. }
  49.  
  50. int main(){
  51.     read2i(n,q);
  52.     lp(i,1,n){
  53.         readi(a[i]);
  54.         update(i, a[i], tree);
  55.         update(i, 1ll*i*a[i], prodTreeL);
  56.         update(i, 1ll*(n-i+1)*a[i], prodTreeR);
  57.     }
  58.  
  59.     while(q--){
  60.         int t,l,r,k;
  61.         read3i(t,l,r);
  62.         if(t == 1){
  63.             readi(k);
  64.             ll ans = query(r, prodTreeR) - query(r-k, prodTreeR) - (n-r) * (query(r, tree) - query(r-k, tree));
  65.             if(l <= r-k) ans += (k+1) * (query(r-k, tree) - query(l-1, tree));
  66.             if(l > 1) ans += query(l-1, prodTreeL) - query(l-k-1, prodTreeL) - max(0, l-k-1) * (query(l-1, tree) - query(l-k-1, tree));
  67.             println(ans);
  68.         }
  69.         else{
  70.             update(l, -a[l] + r, tree);
  71.             update(l, -1ll*l*a[l] + 1ll*l*r, prodTreeL);
  72.             update(l, -1ll*(n-l+1)*a[l] + 1ll*(n-l+1)*r, prodTreeR);
  73.             a[l] = r;
  74.         }
  75.     }
  76. }
  77.  
  78. //freopen("input.txt","r",stdin);
  79. //freopen("output.txt","w",stdout);
  80. //ios::sync_with_stdio(0);cin.tie(0);
RAW Paste Data
Top