Submission #3913175

---

Source Code Expand

#include<iostream>
#include<string>
#include<vector>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<algorithm>
#include<functional>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cassert>
#include<ctime>
#include<random>
using namespace std;

#define mind(a,b) (a>b?b:a)
#define maxd(a,b) (a>b?a:b)
#define absd(x) (x<0?-(x):x)
#define pow2(x) ((x)*(x))
#define rep(i,n) for(int i=0; i<n; ++i)
#define repr(i,n) for(int i=n-1; i>=0; --i)
#define repl(i,s,n) for(int i=s; i<=n; ++i)
#define replr(i,s,n) for(int i=n; i>=s; --i)
#define repf(i,s,n,j) for(int i=s; i<=n; i+=j)
#define repe(e,obj) for(auto e : obj)

#define SP << " " <<
#define COL << " : " <<
#define COM << ", " <<
#define ARR << " -> " <<
#define PNT(STR) cout << STR << endl
#define POS(X,Y) "(" << X << ", " << Y << ")"
#define DEB(A) " (" << #A << ") " << A
#define DEBREP(i,n,val) for(int i=0; i<n; ++i) cout << val << " "; cout << endl
#define ALL(V) (V).begin(), (V).end()
#define INF 1000000007
#define INFLL 1000000000000000007LL
#define EPS 1e-9

typedef unsigned int uint;
typedef unsigned long ulong;
typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;

#define P_TYPE int
typedef pair<P_TYPE, P_TYPE> P;
typedef pair<P, P_TYPE> PI;
typedef pair<P_TYPE, P> IP;
typedef pair<P, P> PP;
typedef priority_queue<P, vector<P>, greater<P> > pvqueue;

#define N 5000007
#define THRESHOLD 4800000

struct Node {
  Node *left, *right;
  ll v, sum, lazy;
  int count;
};

Node gnodes[2][N];
Node *nodes = gnodes[0];
int cur = 0, gcur = 0;

int count(Node *nd) {
  return nd != nullptr ? nd->count : 0;
}

ll sum(Node *nd) {
  return nd != nullptr ? nd->sum : 0;
}

Node *make_node(ll x) {
  Node *nd = &nodes[cur++];
  nd->v = nd->sum = x; nd->count = 1;
  nd->left = nd->right = nullptr;
  nd->lazy = 0;
  return nd;
}

Node *make_node(Node *left, Node *right, ll v = 0, ll lazy = 0) {
  Node *nd = &nodes[cur++];
  nd->left = left; nd->right = right;
  nd->v = v; nd->lazy = lazy;
  int c = 1 + count(left) + count(right);
  nd->sum = v + lazy*c+ sum(left) + sum(right);
  nd->count = c;
  return nd;
}

Node* dfs(Node *nd) {
  Node *left = nullptr, *right = nullptr;
  if(nd->left) left = dfs(nd->left);
  if(nd->right) right = dfs(nd->right);
  Node *r = &(nodes[cur++] = *nd);
  r->left = left; r->right = right;
  return r;
}

Node *rebuild(Node *root) {
  if(cur <= THRESHOLD) {
    return root;
  }
  nodes = gnodes[gcur = (gcur + 1) % 2];
  cur = 0;
  return dfs(root);
}

Node *n_add(Node *nd, ll lazy) {
  if(!nd || lazy == 0) return nd;
  Node *cnd = &(nodes[cur++] = *nd);
  cnd->lazy += lazy;
  cnd->sum += lazy * nd->count;
  return cnd;
}

Node *merge(Node *a, Node *b) {
  if(!a || !b) return !a ? b : a;
  if( rand() % (count(a) + count(b)) < count(a) ) {
    Node *p = n_add(a->left, a->lazy);
    Node *q = merge(n_add(a->right, a->lazy), b);
    return make_node(p, q, a->v + a->lazy, 0);
  } else {
    Node *p = merge(a, n_add(b->left, b->lazy));
    Node *q = n_add(b->right, b->lazy);
    return make_node(p, q, b->v + b->lazy, 0);
  }
}

pair<Node*, Node*> split(Node *nd, int k) {
  if(k <= 0 || !nd) {
    return pair<Node*, Node*>(nullptr, nd);
  }
  if(count(nd) <= k) {
    return pair<Node*, Node*>(nd, nullptr);
  }
  if(k <= count(nd->left)) {
    pair<Node*, Node*> d = split(nd->left, k);
    Node *a = d.first, *b = d.second;
    Node *q = make_node(b, nd->right, nd->v, nd->lazy);
    return make_pair(n_add(a, nd->lazy), q);
  }
  pair<Node*, Node*> d = split(nd->right, k - count(nd->left) - 1);
  Node *a = d.first, *b = d.second;
  Node *p = make_node(nd->left, a, nd->v, nd->lazy);
  return make_pair(p, n_add(b, nd->lazy));
}

int n, q;

Node *root;

int main() {
  cin >> n >> q;
  rep(i, n) {
    ll x; cin >> x;
    Node *nd = make_node(nullptr, nullptr, x, 0);
    root = merge(root, nd);
    root = rebuild(root);
  }
  while(q--) {
    int t, a, b, c, d, v;
    scanf("%d %d %d", &t, &a, &b);
    pair<Node*, Node*> p, q, r;
    Node *left, *mid;
    ll res;
    switch(t) {
    case 1:
      scanf("%d", &v);
      p = split(root, b);
      q = split(p.first, a-1);
      root = merge(q.first, merge(n_add(q.second, v), p.second));
      break;
    case 2:
      scanf("%d %d", &c, &d);
      mid = split(split(root, d).first, c-1).second;
      r = split(root, b);
      left = split(r.first, a-1).first;
      root = merge(left, merge(mid, r.second));
      break;
    case 3:
        res = sum(split(split(root, b).first, a-1).second);
        printf("%lld\n", res);
        break;
    default:
        exit(1);
    }
    root = rebuild(root);
  }
  return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:166:34: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d %d", &t, &a, &b);
                                  ^
./Main.cpp:172:22: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
       scanf("%d", &v);
                      ^
./Main.cpp:178:29: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
       scanf("%d %d", &c, &d);
                             ^

Judge Result