求助大佬,全WA,但是自己调不出来QWQ

P3740 [HAOI2014] 贴海报

LeoPace @ 2022-06-15 17:01:36

#include<bits/stdc++.h>
using namespace std;
struct node{
    int l, r, color=-1;
};
struct poster{
    int l, r;
};
vector<poster> po;
vector<node> tree;
vector<int> a;
set<int> temp;
set<int>::iterator it;
vector<bool> colorVis;
int ans;
inline int getmid(int l, int r) {return l + (r-l)/2;}
void pushdown(int k){
    if(tree[k].l == tree[k].r) return;
    if(tree[k].color==-1) return;
    tree[k*2].color = tree[k].color;
    tree[k*2+1].color = tree[k].color;
    tree[k].color = -1;
}
void build(int k, int l, int r){
    tree[k].l = l, tree[k].r = r;
    if(tree[k].l == tree[k].r) return;
    int mid = getmid(l, r);
    build(k*2, l, mid);
    build(k*2+1, mid+1, r);
}
void dye(int k, int l, int r, int c){
    if(tree[k].color != -1) pushdown(k);
    if(tree[k].l >= l && tree[k].r <= r){
        tree[k].color = c;
        return;
    }
    if(tree[k].color != -1)pushdown(k);
    int mid = getmid(tree[k].l, tree[k].r);
    if(mid >= l) dye(k*2, l, mid, c);
    if(mid < r) dye(k*2+1, mid+1, r, c);
}
void query(int k, int l, int r){
    if(tree[k].color != -1) pushdown(k);
    if(tree[k].l == tree[k].r){
        if(tree[k].color != -1) pushdown(k);
        if(tree[k].color != -1&&!colorVis[tree[k].color]){
            ans++;
            colorVis[tree[k].color] = true;
        }
        return;
    }
    if(tree[k].color != -1) pushdown(k);
    int mid = getmid(tree[k].l, tree[k].r);
    query(k*2, l, mid);
    query(k*2+1, mid+1, r);
}
int main(void){
    int n, m, co = 1;

    #ifndef ONLINE_JUDGE
    freopen("in.in", "r", stdin);
    #endif
    scanf("%d%d", &n, &m);
    colorVis.resize(m+1);
    a.push_back(0);
    po.resize(m+1);
    for(int i = 1; i <= m; i++){
        scanf("%d%d", &po[i].l, &po[i].r);
        if(po[i].r > n) po[i].r = n;
        temp.emplace(po[i].l), temp.emplace(po[i].r);
    }
    it = temp.begin();
    int cur = *it;
    for(it = temp.begin(); it != temp.end(); it++){
        a.push_back(*it);
        if(*it - cur > 1) a.push_back(*it-1);
        cur = *it;
    }
    sort(a.begin(), a.end());
    tree.resize(2*a.size()+1);
    build(1, 1, a.size());
    for(int i = 1; i <= m; i++){
        int ll = lower_bound(a.begin(), a.end(), po[i].l)-a.begin();
        int rr = lower_bound(a.begin(), a.end(), po[i].r)-a.begin();
        dye(1, ll, rr, co++);  
    }
    query(1, 1, a.size());
    printf("%d", ans);
    return 0;
}

|