1. template<class Info, class Merge = plus<Info>>
    2. struct SegTree{
    3.   int n;
    4.   Merge merge;
    5.   vector<Info> info;
    6.   SegTree(int n): n(n), merge(Merge()), info(4 * n) {}
    7.   SegTree(int n, vector<Info> &init): SegTree(n) {
    8.     function<void(int,int,int)> build = [&](int p, int l, int r) {
    9.       if(l == r) {
    10.         info[p] = init[l];
    11.         return;
    12.       }
    13.       int m = (l + r) / 2;
    14.       build(2 * p, l, m);
    15.       build(2 * p + 1, m + 1, r);
    16.       pull(p);
    17.     };
    18.     build(1, 0, n - 1);
    19.   }
    21.   void pull(int p) {
    22.     info[p] = move(merge(info[2 * p], info[2 * p + 1]));
    23.   }
    25.   void modify(int p, int l, int r, int x, const Info &v) {
    26.     if(l == r) {
    27.       info[p] = v;
    28.       return;
    29.     }
    30.     int m = (l + r) / 2;
    31.     if(x <= m) modify(p * 2, l, m, x, v);
    32.     else modify(2 * p + 1, m + 1, r, x, v);
    33.     pull(p);
    34.   }
    36.   void modify(int p, const Info &v) {
    37.     modify(1, 0, n - 1, p, v);
    38.   }
    40.   Info rangeQuery(int p, int l, int r, int x, int y) {
    41.     if(l > y || r < x) {
    42.       return Info();
    43.     }
    44.     if(l >= x && r <= y) return info[p];
    45.     int m = (l + r) / 2;
    46.     return merge(rangeQuery(p * 2, l, m, x, y), rangeQuery(p * 2 + 1, m + 1, r, x, y));
    47.   }
    49.   Info rangeQuery(int l, int r) {
    50.     return rangeQuery(1, 0, n - 1, l, r);
    51.   }
    52. };
    54. struct Info {
    55.   int L, R;
    56.   Info() { L = 0, R = 0; }
    57.   Info(int L, int R): L(L), R(R){}
    58. };
    59. struct Merge {
    60.   Info operator () (const Info &l, const Info &r) const {
    61.     Info t;
    62.     t.L = l.L + r.L - min(l.L, r.R);
    63.     t.R = l.R + r.R - min(l.L, r.R);
    64.     return t;
    65.   }
    66. };
    1. template<class Info, class LazyTag, 
    2.   class Merge, class Mapping, class Composition>
    3. struct LazySegTree{
    4.   int n;
    5.   Merge merge;
    6.   Mapping mapping;
    7.   Composition composition;
    8.   vector<Info> info;
    9.   vector<LazyTag> lazyTag;
    10.   LazySegTree(int n): n(n), merge(Merge()), mapping(Mapping()), 
    11.     composition(Composition()), info(4 * n), lazyTag(4 * n) {}
    12.   LazySegTree(int n, vector<Info> &init): LazySegTree(n) {
    13.     function<void(int,int,int)> build = [&](int p, int l, int r) {
    14.       if(l == r) {
    15.         info[p] = init[l];
    16.         return;
    17.       }
    18.       int m = (l + r) / 2;
    19.       build(2 * p, l, m);
    20.       build(2 * p + 1, m + 1, r);
    21.       pull(p);
    22.     };
    23.     build(1, 0, n - 1);
    24.   }
    26.   void pull(int p) {
    27.     info[p] = move(merge(info[2 * p], info[2 * p + 1]));
    28.   }
    30.   void push(int p, const LazyTag& tag) {
    31.     mapping(tag, info[p]);
    32.     composition(tag, lazyTag[p]);
    33.   }
    35.   void pushdown(int p) {
    36.     push(2 * p, lazyTag[p]);
    37.     push(2 * p + 1, lazyTag[p]);
    38.     lazyTag[p] = LazyTag();
    39.   }
    40.   // 这里是 LazyTag
    41.   void modify(int p, int l, int r, int L, int R, const LazyTag &v) {
    42.     if(l >= L && r <= R) {
    43.       push(p, v);
    44.       return;
    45.     }
    46.     pushdown(p);
    47.     int m = (l + r) / 2;
    48.     if(L <= m) modify(p * 2, l, m, L, R, v);
    49.     if(R > m) modify(2 * p + 1, m + 1, r, L, R, v);
    50.     pull(p);
    51.   }
    53.   void modify(int l, int r, const LazyTag &v) {
    54.     modify(1, 0, n - 1, l, r, v);
    55.   }
    57.   Info rangeQuery(int p, int l, int r, int x, int y) {
    58.     if(l > y || r < x) {
    59.       return Info();
    60.     }
    61.     if(l >= x && r <= y) return info[p];
    62.     int m = (l + r) / 2;
    63.     pushdown(p);
    64.     return merge(rangeQuery(p * 2, l, m, x, y), rangeQuery(p * 2 + 1, m + 1, r, x, y));
    65.   }
    67.   Info rangeQuery(int l, int r) {
    68.     return rangeQuery(1, 0, n - 1, l, r);
    69.   }
    70. };
    72. struct Info {
    73.   ll sum;
    74.   Info(ll sum = 0):sum(sum) {}
    75. };
    77. struct LazyTag {
    78.   ll val;
    79.   LazyTag(ll val = -1):val(val){}
    80. };
    82. struct Merge {
    83.   Info operator () (const Info &l, const Info &r) const {
    84.     Info t;
    85.     t.sum = (l.sum + r.sum);
    86.     return t;
    87.   }
    88. };
    90. struct Mapping {
    91.   void operator () (const LazyTag& tag, Info& info) const {
    92.     if(tag.val != -1) {
    93.       info.sum = tag.val;
    94.     }
    95.   }
    96. };
    98. struct Composition {
    99.   void operator ()(const LazyTag& x, LazyTag& y) const {
    100.     if(x.val != -1) {
    101.       y.val = x.val;
    102.     }
    103.   }
    104. };
    106. void solve() {
    107.   int n, m;
    108.   cin >> n >> m;
    109.   vector<Info> init(n);
    110.   LazySegTree<Info, LazyTag, Merge, Mapping, Composition> seg(n, init);
    111.   while(m --){
    112.     int op;
    113.     cin >> op;
    114.     if(op == 1) {
    115.       int l, r, v;
    116.       cin >> l >> r >> v;
    117.       seg.modify(l, r - 1, LazyTag(v));
    118.     } else {
    119.       int l, r;
    120.       cin >> l;
    121.       cout << seg.rangeQuery(l, l).sum << endl;
    122.     }
    123.   }
    124. }