一个奇怪的问题
查看原帖
一个奇怪的问题
984679
illidan_楼主2024/7/25 22:07

初始化之前二十分,把初始化删了之后九十分,怎么回事呢

#include <bits/stdc++.h>
#define int long long
#define ull unsigned long long
#define id(i,j) (i-1)*m+j
#define endl '\n'

using namespace std;

const int N = 1e6+5;
const int Mx = 0x3f3f3f3f3f3f3f3f;
typedef pair<int,int> PII;

int n,m,ans,T, W, H;
int tree[N<<2], tag[N<<2];
struct node
{
    int x, y, h, w, tt;
}st[N];
map<int, int> mp;
int sw[N], X[N], cnt = 0;

bool cmp(node a, node b)
{
    return a.h < b.h;
} 

void push_up(int id)
{
    tree[id] = max(tree[id<<1], tree[id<<1|1]);
}

void add_tag(int id, int l, int r, int num)
{
    tree[id] += num;
    tag[id] += num;
}

void push_down(int id, int l, int r)
{
    if(tag[id])
    {
        int mid = (l + r) / 2;
        add_tag(id<<1,l,mid,tag[id]);
        add_tag(id<<1|1, mid + 1, r, tag[id]);
        tag[id] = 0;
    }
}

void add(int id, int l, int r, int L, int R, int num, int op)
{
    if(l >= L && r <= R)
    {
        tree[id] += (num * op);
        tag[id] += (num * op);
    }
    else 
    {
        push_down(id,l,r);
        int mid = (l + r) / 2;
        if(mid >= L) add(id<<1,l,mid,L,R,num,op);
        if(mid + 1 <= R) add(id<<1|1,mid + 1, r,L, R,num,op);
        push_up(id);
    }
    //push_up(id);
}

signed main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin>>T;
    while(T --) 
    {
        ans = 0;
        cin>>n>>W>>H;
        // for(int i = 1; i <= N << 2; i++) 
        // {
        //     tree[i] = 0;
        //     tag[i] = 0;
        // }
        mp.clear();
        cnt = 0;
        W --;
        H --;
        for(int i = 1; i <= n; i ++)
        {
            int a, b, c;
            cin>>a>>b>>c;
            X[i * 2 - 1] = a;
            X[i * 2] = a + W;
            st[i * 2 - 1] = {a, a + W, b, c, 1};
            st[i * 2] = {a, a + W, b + H, c, -1};
        }
        n *= 2;
        sort(X + 1, X + 1 + n);
        for(int i = 1; i <= n; i ++)
        {
            if(mp[X[i]] == 0) 
            {
                mp[X[i]] = ++cnt;
                sw[cnt] = X[i];
            }
        }
        sort(st + 1, st + 1 + n, cmp);
        // for(int i = 1; i <= n; i ++)
        // {
        //     cout<<st[i].x<<" "<<st[i].y<<" "<<st[i].h<<" "<<st[i].w<<" "<<st[i].tt<<endl;
        // }
        for(int i = 1; i <= n; i ++)
        {
            int l = mp[st[i].x], r = mp[st[i].y];
            add(1,1,cnt,l,r,st[i].w, st[i].tt);
            ans = max(ans, tree[1]);
        }
        cout<<ans<<endl;
    }      
    return 0;
}
2024/7/25 22:07
加载中...