fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. static struct FastInput {
  4.   static constexpr int BUF_SIZE = 1 << 20;
  5.   char buf[BUF_SIZE];
  6.   size_t chars_read = 0;
  7.   size_t buf_pos = 0;
  8.   FILE *in = stdin;
  9.   char cur = 0;
  10.  
  11.   inline char get_char() {
  12.     if (buf_pos >= chars_read) {
  13.       chars_read = fread(buf, 1, BUF_SIZE, in);
  14.       buf_pos = 0;
  15.       buf[0] = (chars_read == 0 ? -1 : buf[0]);
  16.     }
  17.     return cur = buf[buf_pos++];
  18.   }
  19.  
  20.   inline void tie(int) {}
  21.  
  22.   inline explicit operator bool() {
  23.     return cur != -1;
  24.   }
  25.  
  26.   inline static bool is_blank(char c) {
  27.     return c <= ' ';
  28.   }
  29.  
  30.   inline bool skip_blanks() {
  31.     while (is_blank(cur) && cur != -1) {
  32.       get_char();
  33.     }
  34.     return cur != -1;
  35.   }
  36.  
  37.   inline FastInput& operator>>(char& c) {
  38.     skip_blanks();
  39.     c = cur;
  40.     return *this;
  41.   }
  42.  
  43.   inline FastInput& operator>>(string& s) {
  44.     if (skip_blanks()) {
  45.       s.clear();
  46.       do {
  47.         s += cur;
  48.       } while (!is_blank(get_char()));
  49.     }
  50.     return *this;
  51.   }
  52.  
  53.   template <typename T>
  54.   inline FastInput& read_integer(T& n) {
  55.     // unsafe, doesn't check that characters are actually digits
  56.     n = 0;
  57.     if (skip_blanks()) {
  58.       int sign = +1;
  59.       if (cur == '-') {
  60.         sign = -1;
  61.         get_char();
  62.       }
  63.       do {
  64.         n += n + (n << 3) + cur - '0';
  65.       } while (!is_blank(get_char()));
  66.       n *= sign;
  67.     }
  68.     return *this;
  69.   }
  70.  
  71.   template <typename T>
  72.   inline typename enable_if<is_integral<T>::value, FastInput&>::type operator>>(T& n) {
  73.     return read_integer(n);
  74.   }
  75.  
  76.   #if !defined(_WIN32) || defined(_WIN64)
  77.   inline FastInput& operator>>(__int128& n) {
  78.     return read_integer(n);
  79.   }
  80.   #endif
  81.  
  82.   template <typename T>
  83.   inline typename enable_if<is_floating_point<T>::value, FastInput&>::type operator>>(T& n) {
  84.     // not sure if really fast, for compatibility only
  85.     n = 0;
  86.     if (skip_blanks()) {
  87.       string s;
  88.       (*this) >> s;
  89.       sscanf(s.c_str(), "%lf", &n);
  90.     }
  91.     return *this;
  92.   }
  93. } fast_input;
  94.  
  95. #define cin fast_input
  96. #define ii pair<int,int>
  97. #define fi first
  98. #define se second
  99. //#define int long long
  100. #define FOR(i, a, b) for(int i = (a); i <= (b); i++)
  101. #define ll long long
  102. #define ld double
  103. #define mp make_pair
  104. #define lg2 30
  105. #define iii pair<int,ii>
  106. #define iiii pair<ii,ii>
  107. #define base 29
  108. #define eps 1e-8
  109. #define MASK(i) (1LL << (i))
  110. #define BIT(S, i) (((S) >> (i)) & 1)
  111. int dx[]= {0LL,0LL,1,-1,1,1,-1,-1};
  112. int dy[]= {1,-1,0LL,0LL,1,-1,1,-1};
  113. const int maxn=1e5+1,S=600,size_S=maxn/S+2;
  114. const int mod=1e9+7;
  115.  
  116. struct FEN
  117. {
  118.     int n;
  119.     ll bit1[S+1],bit2[S+1];
  120.     FEN() {};
  121.     FEN(int _n):n(_n+1)
  122.     {
  123.     };
  124.     ll get(ll bit[] ,int r)
  125.     {
  126.         ll ret = 0;
  127.         for (; r > 0; r = (r & (r + 1)) - 1)
  128.             ret += bit[r];
  129.         return ret;
  130.     }
  131.     void update(ll bit[],int idx, int delta)
  132.     {
  133.         for (; idx < n; idx = idx | (idx + 1))
  134.             bit[idx] += delta;
  135.     }
  136.     void updateRange(int l, int r, int v)
  137.     {
  138.         update(bit1, l, (n - l + 1) * v);
  139.         update(bit1, r + 1,-(n - r) * v);
  140.         update(bit2, l, v);
  141.         update(bit2, r + 1, -v);
  142.     }
  143.     ll pre(int u)
  144.     {
  145.         return get(bit1, u) - get(bit2, u) *1LL* (n - u);
  146.     }
  147.  
  148.     ll getRange(int l, int r)
  149.     {
  150.         if(l>r)return 0;
  151.         return pre(r) - (l == 1 ? 0 : pre(l - 1));
  152.     }
  153. } bit[size_S];
  154. int n,L[size_S],R[size_S],q,pos[maxn],p[maxn],cnt,id[maxn];
  155. ll lazy[size_S];
  156. vector<int> nen[size_S];
  157.  
  158. struct Query {
  159.     int type, l, r, x;
  160. } Q[maxn];
  161.  
  162. struct SegmentTree {
  163.     int n;
  164.     vector<ll> node, lazy;
  165.  
  166.     SegmentTree(int n = 0): n(n), node((n << 2) + 5, 0), lazy((n << 2) + 5, 0) {}
  167.  
  168.     void pushDown(int id, int l, int r) {
  169.         ll &t = lazy[id];
  170.         if (t) {
  171.             int mid = (l + r) >> 1;
  172.             node[id << 1] += t * (mid - l + 1);
  173.             node[id << 1 | 1] += t * (r - mid);
  174.             lazy[id << 1] += t;
  175.             lazy[id << 1 | 1] += t;
  176.             t = 0;
  177.         }
  178.     }
  179.  
  180.     void update(int id, int l, int r, int u, int v, int k) {
  181.         if (l > v || r < u) return;
  182.         if (u <= l && r <= v) {
  183.             node[id] += 1LL * (r - l + 1) * k;
  184.             lazy[id] += k;
  185.             return;
  186.         }
  187.         pushDown(id, l, r);
  188.         int mid = (l + r) >> 1;
  189.         update(id << 1, l, mid, u, v, k);
  190.         update(id << 1 | 1, mid + 1, r, u, v, k);
  191.         node[id] = node[id << 1] + node[id << 1 | 1];
  192.     }
  193.  
  194.     ll getSum(int id, int l, int r, int u, int v) {
  195.         if (l > v || r < u) return 0;
  196.         if (u <= l && r <= v) return node[id];
  197.         pushDown(id, l, r);
  198.         int mid = (l + r) >> 1;
  199.         return getSum(id << 1, l, mid, u, v) + getSum(id << 1 | 1, mid + 1, r, u, v);
  200.     }
  201. } IT;
  202.  
  203. namespace Subtask2 {
  204.     bool check() {
  205.         FOR(i, 1, q) if (Q[i].type != 1 && Q[i].type != 3)
  206.             return false;
  207.         return true;
  208.     }
  209.  
  210.     void solve() {
  211. 		IT = SegmentTree(n);
  212.         FOR(i, 1, q) {
  213.             if (Q[i].type == 1) IT.update(1, 1, n, Q[i].l, Q[i].r, Q[i].x);
  214.             else cout << IT.getSum(1, 1, n, Q[i].l, Q[i].r) << '\n';
  215.         }
  216.     }
  217. }
  218.  
  219.  
  220. void solve0(int l,int r,int w)
  221. {
  222.     int x=id[l],y=id[r];
  223.     if(x==y)
  224.     {
  225.         for(int i=l; i<=r; i++)
  226.         {
  227.             bit[x].updateRange(pos[i],pos[i],w);
  228.         }
  229.         return;
  230.     }
  231.     for(int i=x+1; i<=y-1; i++)
  232.     {
  233.         lazy[i]+=w;
  234.     }
  235.     if(R[x]-l+1<=l-1-L[x]+1)
  236.     for(int i=l; i<=R[x]; i++)
  237.     {
  238.         bit[x].updateRange(pos[i],pos[i],w);
  239.     }
  240.     else
  241.     {
  242.         lazy[x]+=w;
  243.         for(int i=L[x];i<=l-1;i++)
  244.         bit[x].updateRange(pos[i],pos[i],-w);
  245.     }
  246.     if(r-L[y]+1<=R[y]-(r+1)+1)
  247.     for(int i=L[y]; i<=r; i++)
  248.     {
  249.         bit[y].updateRange(pos[i],pos[i],w);
  250.     }
  251.     else
  252.     {
  253.         lazy[y]+=w;
  254.         for(int i=r+1;i<=R[y];i++)
  255.         bit[y].updateRange(pos[i],pos[i],-w);
  256.     }
  257. }
  258. void solve1(int l,int r,int w)
  259. {
  260.     for(int i=1;i<=cnt;i++)
  261.     {
  262.         int u=lower_bound(nen[i].begin(),nen[i].end(),l)-nen[i].begin()+1,
  263.             v= (r >= nen[i].back() ? nen[i].size() : upper_bound(nen[i].begin()+u-1,nen[i].end(),r)-nen[i].begin());
  264.             if(u>v)continue;
  265.             if(v-u+1==R[i]-L[i]+1)
  266.             lazy[i]+=w;
  267.            else
  268.             bit[i].updateRange(u,v,w);
  269.     }
  270. }
  271. void solve2(int l,int r)
  272. {
  273.     int x=id[l],y=id[r];
  274.     ll ans=0;
  275.     if(x==y)
  276.     {
  277.         for(int i=l; i<=r; i++)
  278.         {
  279.             ans+=bit[x].getRange(pos[i],pos[i]);
  280.         }
  281.         ans+=1LL*(r-l+1)*lazy[x];
  282.         cout<<ans<<'\n';
  283.         return;
  284.     }
  285.     for(int i=x+1; i<=y-1; i++)
  286.     {
  287.         ans+=bit[i].getRange(1,R[i]-L[i]+1)+(R[i]-L[i]+1)*lazy[i];
  288.     }
  289.     for(int i=l; i<=R[x]; i++)
  290.     {
  291.         ans+=bit[x].getRange(pos[i],pos[i]);
  292.     }
  293.     ans+=1LL*(R[x]-l+1)*lazy[x];
  294.     for(int i=L[y]; i<=r; i++)
  295.     {
  296.         ans+=bit[y].getRange(pos[i],pos[i]);
  297.     }
  298.     ans+=1LL*(r-L[y]+1)*lazy[y];
  299.     cout<<ans<<'\n';
  300. }
  301. void solve3(int l,int r)
  302. {
  303.     ll ans=0;
  304.     for(int i=1;i<=cnt;i++)
  305.     {
  306.         int u=lower_bound(nen[i].begin(),nen[i].end(),l)-nen[i].begin()+1,
  307.             v= (r >= nen[i].back() ? nen[i].size() : upper_bound(nen[i].begin()+u-1,nen[i].end(),r)-nen[i].begin());
  308.             ans+=bit[i].getRange(u,v)+1LL*(v-u+1)*lazy[i];
  309.     }
  310.     cout<<ans<<'\n';
  311. }
  312. signed main()
  313. {
  314.     ios_base::sync_with_stdio(0);
  315.     cin.tie(0);
  316.     cout.tie(0);
  317. #define task "task"
  318.     if(fopen(task".inp","r"))
  319.     {
  320.         freopen(task".inp","r",stdin);
  321.         freopen(task".out","w",stdout);
  322.     }
  323.     cin>>n>>q;
  324.     for(int i=1; i<=n; i++)
  325.     {
  326.          cin>>p[i];
  327.          pos[p[i]]=i;
  328.     }
  329.     FOR(i, 1, q) {
  330.         cin >> Q[i].type >> Q[i].l >> Q[i].r;
  331.         if (Q[i].type <= 1) cin >> Q[i].x;
  332.     }
  333.     if (Subtask2 :: check()) {
  334.         Subtask2 :: solve();
  335.         return 0;
  336.     }
  337.     cnt=0;
  338.     for(int i=1; i<=n; i+=S)
  339.     {
  340.         cnt++;
  341.         L[cnt]=i;
  342.         R[cnt]=min(n,i+S-1);
  343.         bit[cnt]=FEN(R[cnt]-L[cnt]+1);
  344.         for(int j=i; j<=R[cnt]; j++)
  345.         {
  346.             id[j]=cnt;
  347.             nen[cnt].push_back(pos[j]);
  348.         }
  349.         sort(nen[cnt].begin(),nen[cnt].end());
  350.         int j=0;
  351.         for(int j=i;j<=R[cnt];j++)
  352.         {
  353.             pos[j]=lower_bound(nen[cnt].begin(),nen[cnt].end(),pos[j])-nen[cnt].begin()+1;
  354.         }
  355.     }
  356. FOR(i, 1, q)
  357.     {
  358.         int t = Q[i].type;
  359.         if(t==0)
  360.         {
  361.             solve0(Q[i].l,Q[i].r,Q[i].x);
  362.         }
  363.         else if(t==1)
  364.         {
  365.             solve1(Q[i].l,Q[i].r,Q[i].x);
  366.         }
  367.         else if(t==2)
  368.         {
  369.             solve2(Q[i].l,Q[i].r);
  370.         }
  371.         else
  372.         {
  373.             solve3(Q[i].l,Q[i].r);
  374.         }
  375.     }
  376.     cerr <<endl<< "TIME : " << clock() * 0.001 << "s" << endl ;
  377. }
Success #stdin #stdout 0.01s 7776KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/ZOuoBs
language:
C++14 (gcc 8.3)
created:
2 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!