1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54
| #include <iostream> #include <cstdio> #define MAX_N 50000 using namespace std; typedef long long ll; int n, m, cnt; int root[(MAX_N<<2)+500], ls[MAX_N*16*16+500], rs[MAX_N*16*16+500]; ll tr[MAX_N*16*16+500], tag[MAX_N*16*16+500]; inline void updata(int v, int s, int t) {tr[v] = tr[ls[v]]+tr[rs[v]]+tag[v]*(ll)(t-s+1);}
void modify(int &v, int s, int t, int l, int r) { if (!v) v = ++cnt; if (s >= l && t <= r) {tr[v] += (ll)(t-s+1), tag[v]++; return;} int mid = s+t>>1; if (l <= mid) modify(ls[v], s, mid, l, r); if (r >= mid+1) modify(rs[v], mid+1, t, l, r); updata(v, s, t); }
void insert(int v, int s, int t, int l, int r, int x) { modify(root[v], 1, n, l, r); if (s == t) return; int mid = s+t>>1; if (x <= mid) insert(v<<1, s, mid, l, r, x); if (x >= mid+1) insert(v<<1|1, mid+1, t, l, r, x); }
ll calc(int v, int s, int t, int l, int r) { if (!v) return 0; if (s >= l && t <= r) return tr[v]; int mid = s+t>>1; ll ret = tag[v]*(ll)(min(t, r)-max(s, l)+1); if (l <= mid) ret += calc(ls[v], s, mid, l, r); if (r >= mid+1) ret += calc(rs[v], mid+1, t, l, r); return ret; }
ll query(int v, int s, int t, int l, int r, int k) { if (s == t) return s; int mid = s+t>>1; ll tmp = calc(root[v<<1|1], 1, n, l, r); if (k >= tmp+1) return query(v<<1, s, mid, l, r, k-tmp); if (k <= tmp) return query(v<<1|1, mid+1, t, l, r, k); } int main() { scanf("%d%d", &n, &m); while (m--) { int opt, a, b, c; scanf("%d%d%d%d", &opt, &a, &b, &c); if (opt == 1) insert(1, 1, n, a, b, c); if (opt == 2) printf("%lld\n", query(1, 1, n, a, b, c)); } return 0; }
|