fork download
copy 
  1. // #pragma GCC optimize("Ofast,unroll-loops")
  2. // #pragma GCC target("avx,avx2,fma")
  3.  
  4. #include <bits/stdc++.h>
  5. using namespace std;
  6.  
  7. #define ll long long
  8. #define ull unsigned long long
  9. #define dd double
  10. #define ld long double
  11. #define sl(n) scanf("%lld", &n)
  12. #define si(n) scanf("%d", &n)
  13. #define sd(n) scanf("%lf", &n)
  14. #define pll pair <ll, ll>
  15. #define pii pair <int, int>
  16. #define mp make_pair
  17. #define pb push_back
  18. #define all(v) v.begin(), v.end()
  19. #define inf (1LL << 61)
  20. #define loop(i, start, stop, inc) for(ll i = start; i <= stop; i += inc)
  21. #define for1(i, stop) for(ll i = 1; i <= stop; ++i)
  22. #define for0(i, stop) for(ll i = 0; i < stop; ++i)
  23. #define rep1(i, start) for(ll i = start; i >= 1; --i)
  24. #define rep0(i, start) for(ll i = (start-1); i >= 0; --i)
  25. #define ms(n, i) memset(n, i, sizeof(n))
  26. #define casep(n) printf("Case %lld:", ++n)
  27. #define pn printf("\n")
  28. #define pf printf
  29. #define EL '\n'
  30. #define fastio std::ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
  31.  
  32. const ll sz = 22, MAX_N = (1<<14)+10, psz = 4*MAX_N + MAX_N*14, lim = 6;
  33. ll ara[sz], n, idx, tot, l, r;
  34.  
  35. ll tr[psz], Left[psz], Right[psz], root[MAX_N], sufSub[MAX_N], idn;
  36. vector <ll> num;
  37.  
  38. void build(ll lo, ll hi, ll node)
  39. {
  40.     if(lo == hi) {
  41.         tr[node] = 0;
  42.         return;
  43.     }
  44.  
  45.     int mid = lo+hi>>1;
  46.     Left[node] = ++idn, Right[node] = ++idn;
  47.  
  48.     build(lo, mid, Left[node]);
  49.     build(mid+1, hi, Right[node]);
  50.  
  51.     tr[node] = 0;
  52. }
  53.  
  54. ll upd(ll lo, ll hi, ll indx, ll node)
  55. {
  56.     if(lo > indx || hi < indx)
  57.         return node;
  58.  
  59.     ll nnode = ++idn;
  60.  
  61.     if(lo == hi) {
  62.         tr[nnode] = tr[node]+1;
  63.         return nnode;
  64.     }
  65.  
  66.     int mid = lo+hi>>1;
  67.  
  68.     Left[nnode] = upd(lo, mid, indx, Left[node]);
  69.     Right[nnode] = upd(mid+1, hi, indx, Right[node]);
  70.  
  71.     tr[nnode] = tr[ Left[nnode] ] + tr[ Right[nnode] ];
  72.     return nnode;
  73. }
  74.  
  75. ll query(ll lo, ll hi, ll l, ll r, ll lnode, ll rnode)
  76. {
  77.     if(lo > r || hi < l)
  78.         return 0;
  79.  
  80.     if(lo >= l && hi <= r)
  81.         return tr[rnode] - tr[lnode];
  82.  
  83.     int mid = lo+hi>>1;
  84.  
  85.     return query(lo, mid, l, r, Left[lnode], Left[rnode])
  86.         +  query(mid+1, hi, l, r, Right[lnode], Right[rnode]);
  87. }
  88.  
  89. ll solve(ll pos, ll sum, ll x)
  90. {
  91.     if(pos > min(n, lim))
  92.         return 0;
  93.  
  94.     ll nsum = sum+ara[pos], ret = 0;
  95.     tot++;
  96.  
  97.     if(tot >= l && tot <= r)
  98.         ret += (nsum <= x);
  99.  
  100.     ret += solve(pos+1, nsum, x);
  101.  
  102.     if(nsum <= x) {
  103.         ll start = max(1LL, l-tot), stop = min(idx, r-tot);
  104.         ll xp = upper_bound(all(num), x-nsum) - num.begin();
  105.  
  106.         if(start <= stop)
  107.             ret += query(0, idx, 0, xp, root[start-1], root[stop]);
  108.     }
  109.  
  110.     tot += idx;
  111.  
  112.     ret += solve(pos+1, sum, x);
  113.  
  114.     return ret;
  115. }
  116.  
  117. void solve2(ll pos, ll sum)
  118. {
  119.     if(pos > n)
  120.         return;
  121.  
  122.     sufSub[++idx] = sum+ara[pos];
  123.  
  124.     solve2(pos+1, sum+ara[pos]);
  125.     solve2(pos+1, sum);
  126. }
  127.  
  128. void makeSufSub()
  129. {
  130.     solve2(lim+1, 0);
  131.  
  132.     for1(i, idx) num.pb(sufSub[i]);
  133.  
  134.     sort(all(num));
  135.     num.erase(unique(all(num)), num.end());
  136.  
  137.     root[0] = ++idn;
  138.     build(0, idx, root[0]);
  139.  
  140.     for1(i, idx) {
  141.         ll pos = upper_bound(all(num), sufSub[i]) - num.begin();
  142.         root[i] = upd(0, idx, pos, root[i-1]);
  143.     }
  144. }
  145.  
  146. ll countLeq(ll x)
  147. {
  148.     tot = 0;
  149.     ll ret = solve(1, 0, x);
  150.  
  151.     ll start = max(1LL, l-tot), stop = min(idx, r-tot);
  152.  
  153.     if(start <= stop) {
  154.         ll xp = upper_bound(all(num), x) - num.begin();
  155.         ret += query(0, idx, 0, xp, root[start-1], root[stop]);
  156.     }
  157.  
  158.     return ret;
  159. }
  160.  
  161. ll findk(ll k)
  162. {
  163.     ll lo = 1, hi = n*(ll)1e9, ret;
  164.  
  165.     while(lo <= hi) {
  166.         ll mid = lo+hi >> 1;
  167.  
  168.         ll got = countLeq(mid);
  169.  
  170.         if(got >= k) {
  171.             ret = mid;
  172.             hi = mid-1;
  173.         }
  174.         else
  175.             lo = mid+1;
  176.     }
  177.  
  178.     return ret;
  179. }
  180.  
  181. int main()
  182. {
  183.     ll q;
  184.     cin >> n >> q;
  185.  
  186.     for1(i, n) {
  187.         sl(ara[i]);
  188.     }
  189.  
  190.     if(n > lim)
  191.         makeSufSub();
  192.  
  193.     while(q--) {
  194.         ll typ; sl(typ);
  195.  
  196.         if(typ == 1) {
  197.             ll k, c;
  198.             sl(k), sl(c);
  199.  
  200.             ara[k] = c;
  201.         }
  202.         else {
  203.             ll k;
  204.             sl(l), sl(r), sl(k);
  205.  
  206.             pf("%lld\n", findk(k));
  207.         }
  208.     }
  209.  
  210.     return 0;
  211. }
  212.  
Success #stdin #stdout 0s 4856KB
comments (?)
stdin
copy 
3 5
81 93 93
2 4 7 2
2 1 5 5
1 3 5
2 1 5 5
2 4 7 2
stdout
copy 
93
267
179
86
https://ideone.com/rP08FL
language:
C++14 (gcc 8.3)
created:
3 years ago
visibility:
secret

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!