问一个线段树正确性的问题

__Watcher @ 2021-08-10 07:47:03

void change(int o, int l, int r, int s, int t, pair<int,int> x) {
    if(l>=s&&r<=t) {
        if(x>c[o]) c[o]=mp[o]=x;
        mp[o]=c[o];//为什么要写这一行？ 
        return;
    }
    int mid=(l+r)>>1; chuan(o, l, r);
    if(s<=mid) change(o*2, l, mid, s, t, x);
    if(t>mid) change(o*2+1, mid+1, r, s, t, x);
    c[o]=max(c[o*2], c[o*2+1]);
}

by _lbw_ @ 2021-08-10 07:55:58

@邓本永 您可以把整篇代码发一下吗？

by xzggzh1 @ 2021-08-10 07:58:32

打标记肯定要打啊

by __Watcher @ 2021-08-10 08:05:27

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll read() {
    ll x=0, f=1; char ch=' ';
    while(!isdigit(ch)) {ch=getchar(); if(ch=='-') f=-1;}
    while(isdigit(ch)) x=(x<<3)+(x<<1)+(ch^48), ch=getchar();
    return x*f;
}
int n, m, b[1000005], tot, cnt[1000005], dp[1000005], from[1000005];
struct AB{
    int k, l, r;
}d[1000005];
vector<pair<int,int> > g[1000005];
pair<int,int> c[4000005], mp[4000005];
void chuan(int o, int l, int r) {
    c[o*2]=max(c[o*2], mp[o]), c[o*2+1]=max(c[o*2+1], mp[o]);
    mp[o*2]=max(mp[o*2], mp[o]), mp[o*2+1]=max(mp[o*2+1], mp[o]);
    mp[o]={0,0};
}
void change(int o, int l, int r, int s, int t, pair<int,int> x) {
    if(l>=s&&r<=t) {
        if(x>c[o]) c[o]=mp[o]=x;
        return;
    }
    int mid=(l+r)>>1; chuan(o, l, r);
    if(s<=mid) change(o*2, l, mid, s, t, x);
    if(t>mid) change(o*2+1, mid+1, r, s, t, x);
    c[o]=max(c[o*2], c[o*2+1]);
}
pair<int,int> query(int o, int l, int r, int s, int t) {
    if(l>=s&&r<=t) return c[o];
    int mid=(l+r)>>1;
    pair<int,int> ans={0,0}; chuan(o, l, r);
    if(s<=mid) ans=max(ans, query(o*2, l, mid, s, t));
    if(t>mid) ans=max(ans, query(o*2+1, mid+1, r, s, t));
    return ans;
}
int main() {
    cin>>n>>m;
    for(int i=1;i<=m;i++) {
        d[i].k=read(), d[i].l=read(), d[i].r=read();
        b[++tot]=d[i].l, b[++tot]=d[i].r;
    } 
    sort(b+1, b+tot+1);
    for(int i=1;i<=m;i++) {
        d[i].l=lower_bound(b+1, b+tot+1, d[i].l)-b;
        d[i].r=lower_bound(b+1, b+tot+1, d[i].r)-b;
        g[d[i].k].push_back({d[i].l,d[i].r});
    } 
    for(int i=1;i<=n;i++) {
        pair<int,int> now={0,0};
        for(auto tmp:g[i]) {
            now=max(now, query(1, 1, tot, tmp.first, tmp.second));
        }
        dp[i]=now.first+1, from[i]=now.second;
        for(auto tmp:g[i]) {
            change(1, 1, tot, tmp.first, tmp.second, {dp[i],i});
        }
    }
    int id, maxn=0;
    for(int i=1;i<=n;i++) {
        //cout<<dp[i]<<endl;
        if(dp[i]>maxn) {
            maxn=dp[i];
            id=i;
        }
    }
    cout<<n-maxn<<endl;
    int now=id;
    while(now) {
        cnt[now]=1;
        now=from[now];
    }
    for(int i=1;i<=n;i++) {
        if(!cnt[i]) cout<<i<<" ";
    }
}

@lbw

by _lbw_ @ 2021-08-10 08:14:06

@邓本永 我觉得应该这样写

if(x>c[o]) c[o]=x;
if(x>mp[o]) mp[o]=x;

by __Watcher @ 2021-08-10 08:15:57

@lbw 确实，昨晚我一时写叉了，但好像也没错

by _lbw_ @ 2021-08-10 08:17:07

@邓本永 我就是这样写的 /wq

by wrpwrp @ 2021-08-10 09:01:24

D题看假人泪目（

by OrezTsim @ 2021-08-10 09:11:47

不知道，反正我直接 pushdown 的（