官方题解——最简单的一道题

D - 最简单的一道题

​解法是线段树,定义 为区间 到 满足（ ,且对于位置 ，位置 到位置 的这段区间的最小值是位置 的值）的 的数目，每个区间保存区间最小值和 。询问时设一个当前值 ，初始为询问的值，当前区间左边界小于所求位置时，继续递归，大于所求位置时，判断区间最小值是否小于 ，是的话加左子区间继续递归，右子区间不搜索，直接加上 ，更新 。或者区间长度为 且当前值小于 ，答案 并返回。

这个是出题人给的题解，我暴力验证了一下，结果数据放错了，继续背锅。。。
我自己懒得写，有时间写一下吧，先放出题人的代码。

#include<iostream>
#include<bits/stdc++.h>
#include<time.h>
using namespace std;

#define lson (p<<1)
#define rson ( (p<<1) |1)
#define mid ((l+r)>>1)

#define MAX 200005
struct node{
    node(){
        minn = value = add = 0;
    }
    void init(){
        minn = value = add = 0;
    }
    int minn;
    int value;
    int add;
};

struct Segt{
    int arr[MAX];
    node tree[MAX<<2];
    void push_down(int p){
        if(tree[p].add != 0){
            tree[lson].add += tree[p].add;
            tree[rson].add += tree[p].add;
            tree[lson].minn += tree[p].add;
            tree[rson].minn += tree[p].add;
            tree[p].add = 0;
        }

    }

    void push_up(int l, int r, int p){
        //bool flag = true;
        tree[p].minn = min(tree[lson].minn,tree[rson].minn);
        int m = mid;
        int val = tree[lson].minn;
        tree[p].value = que(m+1,val,m+1,r,rson);
    }

    void build(int l, int r, int p){
        tree[p].init();
        if(l == r){
            tree[p].minn = arr[l];
            tree[p].value = 0;
            return;
        }
        int m = mid;
        build(l,m,lson); build(m+1,r,rson);
        push_up(l,r,p);
    }
    void update(int a, int b, int k, int l, int r, int p){
            if(l >= a && r <= b){
                tree[p].minn += k;
                tree[p].add += k;
                return;
            }
            push_down(p);
            int m = mid;
            if(a <= m) update(a,b,k,l,m,lson);
            if(b > m) update(a,b,k,m+1,r,rson);
            push_up(l,r,p);
    }
    int get_val(int pos,int l, int r, int p){
        if(l == r) return tree[p].minn;
        push_down(p);
        int m = mid;
        if(pos <= m) return get_val(pos,l,m,lson);
        else return get_val(pos,m+1,r,rson);
       // push_up(p);
    }
    int que(int a, int& val, int l, int r, int p){
        if(a > r) return 0;
        int m = mid;
     //   cout << l << ' ' << r << endl;
        if(l != r) push_down(p);
        if(l >= a){
            if(tree[p].minn <= val){
                if(l == r){
                 //   cout << "#" << val << ' ' <<  l << ' ' << tree[p].minn << endl;
                    val = tree[p].minn;
                    return 1;
                }
                if(tree[lson].minn <= val){
                    int an = que(a,val,l,m,lson);
                    val = tree[p].minn;
                  //  cout << "@" << val << ' ' << l << ' ' << r << ' ' << an << ' ' << tree[p].value << endl;
                    return an + tree[p].value;
                }else{
                    return que(a,val,m+1,r,rson);
                }
            }else{
                return 0;
            }
        }
        if(a <= m){
            int an = que(a,val,l,m,lson);
            if(val == tree[lson].minn){
                 val = tree[p].minn;
                 return an + tree[p].value;
            }else{
                return an + que(a,val,m+1,r,rson);
            }
        }else{
            return que(a,val,m+1,r,rson);
        }
    }



};
Segt segt;

void make_input(ostream & out){
    srand(time(NULL));
    int limit1 = 200000;
    int limitk = 10000;
    int n = rand()%limit1 + 5;
    int m = rand()%limit1 + 5;
    out << n << ' ' << m << endl;
    for(int i = 1; i <= n; i++){
        out << rand()%limitk << ' ';
    }
    out << endl;
    for(int i = 1; i <= m; i++){
        int f = rand()%2;
        if(f){
            int l = 1 + rand() %(n-1);
            int r = l + rand() %(n - l);
            int k = rand() % limitk;
            out << "c " << l << ' ' << r << ' ' << k << endl;
        }else{
            int x = 1 + rand() %(n-1);
            out << "q " << x << endl;
        }
    }
}
/*
5 5
1 2 3 4 3
q 3
c 1 3 3
q 2
c 5 5 4
q 5

*/
void make_ans(istream & in, ostream & out){
    int n, m;
    in >> n >> m;
    for(int i = 1; i <= n; i++){
        in >> segt.arr[i];
    }
    segt.build(1,n,1);
    while(m--){
        char ch;
      /*  cout << "------" << endl;
        for(int i = 1; i <= n; i++) cout << segt.get_val(i,1,n,1) << ' '; cout << endl;
        cout << "------" << endl;*/
        in >> ch;
        if(ch == 'c'){
            int l, r, k;
            in >> l >> r >> k;
            segt.update(l,r,k,1,n,1);
        }else{
            int x;
            in >> x;
            int val = segt.get_val(x,1,n,1);
          //  cout << val << endl;
            out << segt.que(x+1,val,1,n,1) << endl;
        }
    }
}

int main(void){
    make_ans(cin,cout);
    return 0;
}