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 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104
| #define REP(i, s, e) for (int i = s; i <= e; i++) #define DREP(i, s, e) for (int i = s; i >= e; i--) #define DEBUG fprintf(stderr, "Passing [%s] in Line %d\n", __FUNCTION__, __LINE__)
#define chkmax(a, b) a = max(a, b) #define chkmin(a, b) a = min(a, b)
#include <cstdio> #include <iostream>
using namespace std;
template <typename T> T read() { T ans = 0, p = 1; char c = getchar(); while (!isdigit(c)) { if (c == '-') p = -1; c = getchar(); } while (isdigit(c)) { ans = ans * 10 + c - 48; c = getchar(); } return ans * p; }
#define mid (l + r >> 1) #define lson p -> ls, l, mid #define rson p -> rs, mid + 1, r
int n, m;
struct node_inside { node_inside *ls, *rs; int sum, tag; node_inside() : sum(0), tag(0), ls(NULL), rs(NULL) {} }; int query(node_inside *x, bool flag = 1) {return x != NULL ? x -> sum * flag + x -> tag * (flag ^ 1) : 0;} void update(node_inside *&p, int l, int r, int L, int R) { if (p == NULL) p = new node_inside(); if (L == l && r == R) p -> tag++; else if (L > mid) update(rson, L, R); else if (R <= mid) update(lson, L, R); else { update(lson, L, mid); update(rson, mid + 1, R); } p -> sum += R - L + 1; } int query(node_inside *&p, int l, int r, int L, int R) { if (p == NULL) return 0; if (L == l && r == R) return query(p); int res = (R - L + 1) * query(p, 0); if (R <= mid) return query(lson, L, R) + res; else if (L > mid) return query(rson, L, R) + res; else return query(lson, L, mid) + query(rson, mid + 1, R) + res; } struct node_outside { node_inside *rt; node_outside *ls, *rs; node_outside() : ls(NULL), rs(NULL), rt(NULL){} };
node_outside *T; void update(node_outside *&p, int l, int r, int L, int R, int pos) { if (p == NULL) p = new node_outside(); update(p -> rt, 1, n, L, R); if (l == r) return; if (pos <= mid) update(lson, L, R, pos); else update(rson, L, R, pos); } int query(node_outside *&p, int l, int r, int L, int R, int pos) { if (l == r) return l; int cnt = p -> rs == NULL ? 0 : query(p -> rs -> rt, 1, n, L, R); if (cnt >= pos) return query(rson, L, R, pos); else return query(lson, L, R, pos - cnt); }
int main() { #ifdef CraZYali freopen("3110.in", "r", stdin); freopen("3110.out", "w", stdout); #endif cin >> n >> m; while (m --> 0) { int opt(read<int>()), a(read<int>()), b(read<int>()), c(read<int>()); if (opt == 1) update(T, 1, n, a, b, c); else printf("%d\n", query(T, 1, n, a, b, c)); } return 0; }
|