fork download
copy 
  1. //#pragma GCC optimize("Ofast,unroll-loops")
  2. //#pragma GCC target("avx2,tune=native")
  3. #include <bits/stdc++.h>
  4. using namespace std;
  5.  
  6. #define file "query"
  7. #define ff(i, a, b) for(auto i=(a); i<=(b); ++i)
  8. #define ffr(i, b, a) for(auto i=(b); i>=(a); --i)
  9. #define nl "\n"
  10. #define ss " "
  11. //#define pb push_back
  12. #define pb emplace_back
  13. #define fi first
  14. #define se second
  15. #define sz(s) (int)s.size()
  16. #define all(s) (s).begin(), (s).end()
  17. #define ms(a,x) memset(a, x, sizeof (a))
  18. #define cn continue
  19. #define re exit(0)
  20.  
  21. typedef long long ll;
  22. typedef unsigned long long ull;
  23. typedef long double ld;
  24. typedef vector<int> vi;
  25. typedef vector<ll> vll;
  26. typedef pair<int, int> pii;
  27. typedef pair<ll, ll> pll;
  28. typedef vector<pii> vpii;
  29. typedef vector<pll> vpll;
  30.  
  31. mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
  32. ll ran(ll l, ll r)
  33. {
  34.     return uniform_int_distribution<ll> (l, r)(rng);
  35. }
  36.  
  37. inline void rf()
  38. {
  39.     ios_base::sync_with_stdio(false);
  40.     cin.tie(nullptr); cout.tie(nullptr);
  41.     if(fopen(file".inp","r"))
  42.     {
  43.         freopen(file".inp","r",stdin);
  44.         freopen(file".out","w",stdout);
  45.     }
  46. }
  47.  
  48. const int mod=1e9+7;
  49. const int maxn=3e5+15;
  50. const ll inf=5e16;
  51.  
  52. template<typename T> inline void add(T &x, const T &y)
  53. {
  54.     x+=y;
  55.     if(x>=mod) x-=mod;
  56.     if(x<0) x+=mod;
  57. }
  58.  
  59. template<typename T> inline bool maxi(T &a, T b)
  60. {
  61.     if(a>=b) return 0;
  62.     a=b; return 1;
  63. }
  64.  
  65. template<typename T> inline bool mini(T &a, T b)
  66. {
  67.     if(a<=b) return 0;
  68.     a=b; return 1;
  69. }
  70.  
  71. int n, q;
  72. int st[2][maxn], ed[2][maxn], timer[2];
  73. int h[maxn];
  74. vi g[maxn];
  75.  
  76. void dfs(int u, int par)
  77. {
  78.     ff(i ,0, 1) st[i][u]=timer[i]+1;
  79.     ++timer[h[u]&1 ];
  80.     for(auto v:g[u]) if(v!=par) h[v]=h[u]+1, dfs(v, u);
  81.     ff(i ,0, 1) ed[i][u]=timer[i];
  82. }
  83.  
  84. struct node
  85. {
  86.     int lazy;
  87.     vi val;
  88.  
  89.     node()
  90.     {
  91.         lazy=0;
  92.         val.clear();
  93.     }
  94. };
  95.  
  96. inline node combine(const node &l, const node &r)
  97. {
  98.     auto &y=l.val, &z=r.val;
  99.     if(y.empty()) return r;
  100.     if(z.empty()) return l;
  101.     node ans;
  102.     auto &x=ans.val;
  103.     int i=0, j=0, sz=min(15, sz(y)+sz(z));
  104.     x.reserve(sz);
  105.     while(i<sz(y) && j<sz(z) && i+j<sz)
  106.     {
  107.         if(y[i]>=z[j]) x.pb(y[i]), ++i;
  108.         else x.pb(z[j]), ++j;
  109.     }
  110.     while(i<sz(y) && i+j<sz) x.pb(y[i]), ++i;
  111.     while(j<sz(z) && i+j<sz) x.pb(z[j]), ++j;
  112.     return ans;
  113. }
  114.  
  115. struct it
  116. {
  117.     node t[maxn*2];
  118.  
  119.     void build(int id, int l, int r)
  120.     {
  121.         if(l==r) return t[id].val.assign(1, 0), void();
  122.         int mid=(l+r)>>1;
  123.         build(id<<1, l, mid); build(id<<1|1, mid+1, r);
  124.         t[id]=combine(t[id<<1], t[id<<1|1]);
  125.     }
  126.  
  127.     inline void push(int id)
  128.     {
  129.         if(t[id].lazy==0) return;
  130.         ff(i, id*2, id*2+1)
  131.         {
  132.             t[i].lazy+=t[id].lazy;
  133.             for(auto &x:t[i].val) x+=t[id].lazy;
  134.         }
  135.         t[id].lazy=0;
  136.     }
  137.  
  138.     void upd(int id, int l, int r, int u, int v, int val)
  139.     {
  140.         if(r<u || v<l) return;
  141.         if(u<=l && r<=v)
  142.         {
  143.             t[id].lazy+=val;
  144.             for(auto &x:t[id].val) x+=val;
  145.             return;
  146.         }
  147.         int mid=(l+r)>>1;
  148.         push(id);
  149.         upd(id<<1, l, mid, u, v, val);
  150.         upd(id<<1|1, mid+1 ,r, u, v ,val);
  151.         t[id]=combine(t[id<<1], t[id<<1|1] );
  152.     }
  153.  
  154.     node get(int id, int l, int r, int u, int v)
  155.     {
  156.         if(r<u || v<l) return node();
  157.         if(u<=l && r<=v) return t[id];
  158.         int mid=(l+r)>>1;
  159.         push(id);
  160.         node x=get(id<<1, l, mid, u, v), y=get(id<<1|1, mid+1, r, u, v);
  161.         return combine(x, y);
  162.     }
  163.  
  164. } t0, t1;
  165.  
  166. signed main()
  167. {
  168.     rf();
  169.     int sub; cin>>sub;
  170.     cin>>n;
  171.     ff(u, 2, n)
  172.     {
  173.         int v; cin>>v; g[v].pb(u);
  174.     }
  175.     dfs(1, 0);
  176.     int n0=timer[0], n1=timer[1];
  177.     t0.build(1, 1, n0); t1.build(1 ,1, n1);
  178.     cin>>q;
  179.     while(q--)
  180.     {
  181.         string op; cin>>op;
  182.         if(op[0]=='a')
  183.         {
  184.             int u, val; cin>>u>>val;
  185.             if(h[u]&1) val=-val;
  186.             t0.upd(1, 1, n0, st[0][u] ,ed[0][u], val);
  187.             t1.upd(1, 1, n1, st[1][u] ,ed[1][u], -val);
  188.         }
  189.         else if(op[0]=='g')
  190.         {
  191.             int u; cin>>u;
  192.             node ans;
  193.             if(h[u]%2==0) ans=t0.get(1, 1, n0, st[0][u], st[0][u]);
  194.             else ans=t1.get(1, 1, n1, st[1][u], st[1][u]);
  195.             cout<<ans.val[0]<<ss;
  196.         }
  197.         else
  198.         {
  199.             int u, k; cin>>u>>k;
  200.             node l=t0.get(1, 1, n0, st[0][u], ed[0][u]);
  201.             node r=t1.get(1, 1, n1, st[1][u], ed[1][u]);
  202.             node ans=combine(l ,r);
  203.             if(ans.val.size()<k) cout<<0<<ss;
  204.             else cout<<ans.val[k-1]<<ss;
  205.         }
  206.     }
  207.     re;
  208. }
  209.  
Success #stdin #stdout 0.02s 50292KB
comments (?)
stdin
copy 
1
7
1 2 2 4 1 6
18
add 1 1
get 1
get 2
get 3
get 4
get 5
get 6
get 7
add 2 5
add 7 -3
pos 1 1
pos 1 2
pos 1 3
pos 1 4
pos 1 5
pos 1 6
pos 1 7
pos 1 8
stdout
copy 
1 -1 1 1 -1 -1 1 4 4 1 -1 -2 -4 -4 0
https://ideone.com/Qq9z58
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!