fork download
copy 
  1. // ROOT : DRAGON3012009 : WA in Real Life
  2. #include <bits/stdc++.h>
  3. #define FOR(i,l,r) for(int i = l ; i <= r ; i ++)
  4. #define FORD(i,r,l) for(int i = r ; i >= l ; i --)
  5. #define REP(i, a ) for(int i = 0 ; i < a ; i ++ )
  6. #define compare(v) sort((v).begin(), (v).end()); (v).erase(unique((v).begin(), (v).end()), (v).end());
  7. #define ll long long
  8. #define el "\n"
  9. #define fi first
  10. #define se second
  11. #define _ROOT_ int main()
  12. #define M 1000000007
  13. #define MAXN 200001
  14. #define BLOCK 600
  15. #define Bit(i) (1LL << i )
  16. #define INF (1ll<<30)
  17. #define NAME "file"
  18. #define debug(a) cout << #a << " = " << a << endl;
  19. using namespace std;
  20.  
  21. ll n, m, q ;
  22. ll a[MAXN] ;
  23. ll p[MAXN ] ;
  24. ll belong[MAXN ] ;
  25. ll blockSum[MAXN ] ;
  26. ll belongP[MAXN ] ;
  27. ll res[MAXN ] ;
  28. ll lienquan[BLOCK + 1 ][BLOCK + 1 ] ;
  29. ll lazy[MAXN ] ;
  30. vector<ll> adj[MAXN ] ;
  31. struct Data {
  32.     ll t, l, r, x ;
  33. } que[MAXN ] ;
  34.  
  35. void buildBlock(ll curBlock ) {
  36.     FOR(j, belong[1], belong[n]) {
  37.         ll st = j * BLOCK, fin = (j + 1) * BLOCK - 1;
  38.         ll L = curBlock * BLOCK, R = (curBlock + 1 ) * BLOCK - 1 ;
  39.         L = max(L, 1LL ) ;
  40.         R = min(n, R ) ;
  41.         FOR(k, L, R ) if(st <= p[k] && p[k] <= fin ) lienquan[curBlock][j] ++ ;
  42.     }
  43.     FOR(j , 1, belong[n]) lienquan[curBlock][j] += lienquan[curBlock][j - 1] ;
  44. }
  45.  
  46. void update(ll l, ll r, ll x ) {
  47.     if(belong[l] == belong[r]) {
  48.         FOR(i, l, r ) {
  49.             a[p[i]] += x ;
  50.             blockSum[p[i] / BLOCK] += x ;
  51.         }
  52.     } else {
  53.         for(ll i = l ; belong[i] == belong[l] ; i ++ ) {
  54.             a[p[i]] += x ;
  55.             blockSum[p[i] / BLOCK] += x ;
  56.         }
  57.         for(ll i = r ; belong[i] == belong[r] ; i -- ) {
  58.             a[p[i]] += x ;
  59.             blockSum[p[i] / BLOCK] += x ;
  60.  
  61.         }
  62.         FOR(i, belong[l] + 1, belong[r] - 1 ) lazy[i] += x ;
  63.     }
  64. }
  65.  
  66. ll get(ll l , ll r ) {
  67.     ll ans = 0 ;
  68.     if(belong[l] == belong[r]) {
  69.         FOR(i , l , r ) {
  70.         ans += a[i] + lazy[belongP[i] ] ;
  71.         }
  72.     }else {
  73.         for(ll i = l ; belong[i] == belong[l] ; i ++ ) {
  74.                    ans += a[i] + lazy[belongP[i] ] ;
  75.         }
  76.         for(ll i = r ; belong[i] == belong[r] ; i -- ) {
  77.                ans += a[i] + lazy[belongP[i] ] ;
  78.         }
  79.         FOR(i, belong[l] + 1, belong[r] - 1 ) {
  80.         ans += blockSum[i] ;
  81.         }
  82.         FOR(i , belong[1] , belong[n]) {
  83.       if(lienquan[i][belong[r] - 1 ] >= lienquan[i][belong[l]] )  ans += (lienquan[i][ belong[r] - 1 ] - lienquan[i][ belong[l] ] ) * lazy[i] ;
  84.         }
  85.     }
  86.     return ans ;
  87. }
  88.  
  89. void undo_prefix_block(ll curBlock ) {
  90.     FORD(j , belong[n] , 1 ) lienquan[curBlock][j] -= lienquan[curBlock][j - 1 ] ;
  91. }
  92.  
  93. void rebuild_prefix_block(ll curBlock ) {
  94.     FOR(j , 1 , belong[n]) lienquan[curBlock][j] += lienquan[curBlock][j - 1] ;
  95. }
  96.  
  97. void manual_fix_block(ll curBlock ) {
  98.     ll L = curBlock * BLOCK , R = (curBlock + 1 ) * BLOCK - 1 ;
  99.     L = max(1LL , L ) ;
  100.     R = min(R , n ) ;
  101.     FOR(i , L , R ) {
  102.     a[p[i]] += lazy[curBlock ] ;
  103.     blockSum[p[i] / BLOCK] += lazy[curBlock ] ;
  104.     }
  105.     lazy[curBlock] = 0 ;
  106. }
  107.  
  108. void addBlock(ll curBlock , ll pos , ll value ) {
  109.     lienquan[curBlock][p[pos] / BLOCK] += value ;
  110. }
  111.  
  112. void swap_perm(ll l , ll r ) {
  113.     if(belong[l] == belong[r]) {
  114.     swap(p[l] , p[r]) ;
  115.     return ;
  116.     }
  117.     manual_fix_block(belong[l]) ;
  118.     manual_fix_block(belong[r]) ;
  119.  
  120.     undo_prefix_block(belong[l] ) ;
  121.     undo_prefix_block(belong[r] ) ;
  122.  
  123.     addBlock(belong[l] , l , -1 ) ;
  124.     addBlock(belong[r] , r , -1 ) ;
  125.  
  126.     belongP[p[l]] = r / BLOCK ;
  127.     belongP[p[r]] = l / BLOCK ;
  128.  
  129.     swap(p[l] , p[r]) ;
  130.  
  131.     addBlock(belong[l] , l , 1 ) ;
  132.     addBlock(belong[r] , r , 1 ) ;
  133.  
  134.     rebuild_prefix_block(belong[l]) ;
  135.     rebuild_prefix_block(belong[r]) ;
  136.  
  137. }
  138.  
  139. void dfs(ll u ) {
  140.     if(que[u].t == 2 ) {
  141.         res[u] = get(que[u].l , que[u].r ) ;
  142.     }
  143.     for(ll v : adj[u]) {
  144.         if(que[v].t == 1 ) {
  145.             update(que[v].l, que[v].r, que[v].x ) ;
  146.         } else if(que[v].t == 3 ) {
  147.             swap_perm(que[v].l, que[v].r ) ;
  148.         }
  149.         dfs(v ) ;
  150.         if(que[v].t == 1 ) {
  151.             update(que[v].l, que[v].r, - que[v].x ) ;
  152.         } else if(que[v].t == 3 ) {
  153.             swap_perm(que[v].l, que[v].r ) ;
  154.         }
  155.     }
  156. }
  157.  
  158. void init() {
  159.     cin >> n >> q ;
  160.     FOR(i, 1, n ) cin >> a[i] ;
  161.     FOR(i, 1, n ) cin >> p[i] ;
  162.     FOR(i , 1 , n ) blockSum[i / BLOCK ] += a[i];  
  163.     FOR(i, 1, n ) belong[i] = i / BLOCK ;
  164.     FOR(i, 1, n ) belongP[p[i]] = i / BLOCK ;
  165.     ll last = -1 ;
  166.     FOR(i, 1, n ) {
  167.         if(last != belong[i]) {
  168.             last = belong[i] ;
  169.             buildBlock(last ) ;
  170.         }
  171.     }
  172.     FOR(i , 1 , q ) {
  173.     cin >> que[i].t >> que[i].l ;
  174.     if(que[i].t == 4 ) {
  175.         adj[que[i].l - 1 ].push_back(i) ;
  176.         continue ;
  177.     }else adj[i - 1].push_back(i) ;
  178.     cin >> que[i].r ;
  179.     if(que[i].t ==  1 ) cin >> que[i].x ;
  180.     }
  181. }
  182.  
  183. void solve() {
  184.     dfs(0 ) ;
  185.     FOR(i, 1, q ) if(que[i].t == 2 ) cout << res[i] << el ;
  186. }
  187.  
  188.  
  189. _ROOT_ {
  190. //    freopen(NAME".inp", "r", stdin);
  191. //    freopen(NAME".out", "w", stdout) ;
  192.     ios_base::sync_with_stdio(0);
  193.     cin.tie(0);
  194.     cout.tie(0);
  195.     int t = 1; // cin >> t ;
  196.     while(t--) {
  197.         init();
  198.         solve();
  199.     }
  200.     return (0&0);
  201. }
  202.  
Success #stdin #stdout 0.01s 9572KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/CquASs
language:
C++14 (gcc 8.3)
created:
1 day 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!