请求添加hack

#include <bits/stdc++.h>
using namespace std;
int main()
{
    freopen ("hack3.in" , "w" , stdout);

    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    int INF = 1e6 , cnt = 0;
    int n = 1e6 , m = 3000;
    cout << n << ' ' << m << '\n';
    for (int i=1 ; i<=n ; i++)
    {
        if (i&1) cout << 1+cnt << ' ';
        else 
        {
            cout << INF-cnt << ' ';
            cnt++;
        }
    }
    cout << '\n';
    cnt = 1;
    while (m--)
    {
        cout << "A 1 " << n << ' ' << cnt << " \n";
        cnt+=100;
    }
    return 0;
}

上述数据生成器可以将水过第二组hack的线段树卡掉，如一下这种线段树

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

const int N = 1e6+10 , INF = 1e9;

int n , m;
int a[N];

struct node 
{
    int l , r;
    int mx , semx , cntmx;
    int mn , semn , cntmn;
    int add;
}tr[N<<2];

void pushup (node &rt , node l , node r)
{
    if (l.mx==r.mx) //处理最大值 
    {
        rt.mx = l.mx , rt.cntmx = l.cntmx+r.cntmx;
        rt.semx = max(l.semx , r.semx);
    }
    else if (l.mx>r.mx)
    {
        rt.mx = l.mx , rt.cntmx = l.cntmx;
        rt.semx = max(l.semx , r.mx);
    }
    else 
    {
        rt.mx = r.mx , rt.cntmx = r.cntmx;
        rt.semx = max(r.semx , l.mx);
    }
    if (l.mn==r.mn) //处理最小值
    {
        rt.mn = l.mn , rt.cntmn = l.cntmn+r.cntmn;
        rt.semn = min(l.semn , r.semn);
    } 
    else if (l.mn<r.mn)
    {
        rt.mn = l.mn , rt.cntmn = l.cntmn;
        rt.semn = min(l.semn , r.mn);
    }
    else 
    {
        rt.mn = r.mn , rt.cntmn = r.cntmn;
        rt.semn = min(r.semn , l.mn);
    }
}
void pushup (int u)
{
    pushup (tr[u] , tr[u<<1] , tr[u<<1|1]);
}

void build (int u , int l , int r)
{
    if (l==r)
    {
        tr[u] = {l , r , a[l] , -INF , 1 , a[l] , INF , 1 , 0};
    }
    else 
    {
        tr[u].l = l , tr[u].r = r;
        int mid = (l+r)>>1;
        build (u<<1 , l , mid) , build (u<<1|1 , mid+1 , r);
        pushup (u);
    }
}

void update (int u , int c) //偷懒少写几次更新 
{
    tr[u].add += c;
    tr[u].mn += c , tr[u].mx += c;
    tr[u].semn += c , tr[u].semx += c;  
}

void pushdown (int u)
{
    if (tr[u].add)
    {
        update (u<<1 , tr[u].add) , update (u<<1|1 , tr[u].add);
        tr[u].add = 0;
    }
}

void modify (int u , int l , int r , int c)
{
    if (tr[u].l>=l && tr[u].r<=r)
    {
        update (u , c);
    }
    else 
    {
        pushdown (u);
        int mid = (tr[u].l+tr[u].r)>>1;
        if (l<=mid)
        {
            modify (u<<1 , l , r , c);
        }
        if (r>mid)
        {
            modify (u<<1|1 , l , r , c);
        }
        pushup (u);
    }
}

int query (int u , int l , int r , int c)
{
    if (tr[u].l>=l && tr[u].r<=r)
    {
        if (tr[u].mn>=c) return tr[u].r-tr[u].l+1;
        if (tr[u].mx<c) return 0;
        if (tr[u].mx>=c && tr[u].semx<c) return tr[u].cntmx;
        if (tr[u].mn<c && tr[u].semn>=c) return tr[u].r-tr[u].l+1-tr[u].cntmn;
    }
    pushdown (u);
    int mid = (tr[u].l+tr[u].r)>>1;
    int res = 0;
    if (l<=mid)
    {
        res += query (u<<1 , l , r , c);
    }
    if (r>mid)
    {
        res += query (u<<1|1 , l , r , c);
    }
    return res;
}

int main()
{
//  freopen ("1.in" , "r" , stdin);
//  freopen ("std.out" , "w" , stdout);

    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    cin >> n >> m;
    for (int i=1 ; i<=n ; i++)
    {
        cin >> a[i];
    }

    build (1 , 1 , n);

    while (m--)
    {
        string s;
        int l , r , c;
        cin >> s >> l >> r >> c;
        if (s=="A")
        {
            cout << query (1 , l , r , c) << '\n';
        }
        else 
        {
            modify (1 , l , r , c);
        }
    }
    return 0;
}