Debug 小練習 ヾ(≧▽≦*)o

簡單的小情境

1. 妳要找一個陣列的最大連續和，所以寫出了這份 code！欸? 為什麼答案都是
   $0$ 呢 ヽ(*。>Д<)o゜
   題目: CSES - Maximum Subarray Sum

int n;cin>>n;
vector<int> a(n);
for(int i=0;i<n;i++){
    int x;cin>>x;
    a.push_back(x);
}
int ans=0,mx=0;
for(int i=0;i<n;i++){
    mx=max(a[i],mx+a[i]);
    ans=max(ans,mx);
}
cout<<ans<<"\n";

2. 現在妳有一個二維陣列，妳想要建出這個陣列的二維前綴和！可是跑不出答案欸 QQ

int n,m;
cin>>n>>m;
int arr[n+1][m+1]{},pre[n+1][n+1]{};
for(int i=1;i<=n;i++){
    for(int j=1;j<=m;i++){
        cin>>arr[i][j];
    }
}
for(int i=1;i<=n;i++){
    for(int j=1;j<=m;j++){
        pre[i][j]=arr[i][j]+pre[i-1][j]+pre[i][j-1]-pref[i-1][j-1];
    }
}

3. 現在妳在寫 dsu，要計算連通塊的數量，可是為什麼答案跑不出來 QQ

int cnt;

int findDSU(int a){
    if(dsu[a]!=a) return dsu[a]=findDSU(a);
    return dsu[a];
}

void unionDSU(int a,int b){
    a=findDSU(a);
    b=findDSU(b);
    if(a==b) return;
    dsu[a]=b;
    cnt--;
}

signed main(){
    fastio

    int n,m; cin>>n>>m;
    cnt=n;
    for(int i=0;i<n;i++){
        int u,v; cin>>u>>v;
        unionDSU(u,v);
    }
    cout<<cnt<<"\n";
}

4. 妳要建凸包，然後找凸包的面積*2。可是為什麼答案很奇怪 R QwQ

pair<int,int> operator - (pair<int,int> a,pair<int,int> b){
    return {a.first-b.first,a.second-b.second};
}

int operator ^ (pair<int,int> a,pair<int,int> b){
    return a.first*b.second-a.second*b.first;
}

void convex_hull(vector<pair<int,int>> points){
    sort(points.begin(),points.end());
    vector<pair<int,int>> hull;
    for(int t=0;t<2;++t){
        int sz=hull.size();
        for(auto p:points){
            while(hull.size()>=sz+2&&(((hull[hull.size()-1]-hull[hull.size()-2])^(p-hull[hull.size()-2]))<0)){
                hull.pop_back();
            }
            hull.push_back(p);
        }
        hull.pop_back();
        reverse(points.begin(),points.end());
    }
    points=hull;
}

signed main(){
    fastio
        
    int n;cin>>n;
    vector<pair<int,int>> points;
    for(int i=0;i<n;i++){
        int a,b;cin>>a>>b;
        v.push_back({a,b});
    }
    convex_hull(points);
    int ans=0;
    for(int i=0;i<n;i++){
        ans += (points[i]^points[(i+1)%n]);
    }
    cout<<abs(ans)<<"\n";
}

5. 妳在寫簡單的單點修改，區間加值的線段樹。可是答案 QQ
   題目: CSES - Range Sum Queries

int tree[MAXN*4], a[MAXN];
int merge(int a,int b){
    return a+b;
}
 
void build(int l,int r,int id){
    if(l==r){
        tree[id]=a[l];
    }
    int mid=(l+r)/2;
    build(l,mid,id*2);
    build(mid+1,r,id*2+1);
    tree[id]=merge(tree[id*2],tree[id*2+1]);
}
 
int query(int ql,int qr,int l,int r,int id){
    if(ql<=l&&qr>=r){
        return tree[id];
    }
    int mid=(l+r)/2;
    if(ql>mid) return query(ql,qr,mid+1,r,id*2+1);
    if(qr<=mid) return query(ql,qr,l,mid,id*2);
    return merge(query(ql,qr,l,mid,id*2),query(ql,qr,mid+1,r,id*2+1));
}
 
void modify(int pos,int val,int l,int r,int id){
    if(l==r){
        tree[id]=val;
        return;
    }
    int mid=(l+r)/2;
    if(pos>mid) modify(pos,val,mid+1,r,id*2+1);
    else modify(pos,val,l,mid,id*2);
    tree[id]=merge(tree[id*2],tree[id*2+1]);
}

signed main(){
    int n,k; cin>>n>>k;
    for(int i=1;i<=n;i++) cin >> a[i];
    while(k--){
        int t,a,b; cin>>t>>a>>b;
        if(t==1){
            modify(a,b,1,n,1);
        }else{
            cout<<query(a,b,1,n,1)<<"\n";
        }
    }
}

來挑戰過去自己 debug 不出來的 code ㄅ ( •̀ ω •́ )✧

1. 妳在寫線段樹的區間詢問最大連續和，哪裡出錯了呢 QQ

const int MAXN=1e5+5;
const int MOD=998244353;
 
int a[MAXN]{},tree[MAXN*4]{},tag[MAXN*4]{},sum[MAXN*4]{},pref[MAXN*4]{},suf[MAXN*4]{};
 
void build(int l,int r,int id){
    if(l==r) tree[id]=a[l];
    int mid=l+r>>1;
    build(l,mid,id<<1);
    build(mid+1,r,id<<1|1);
}
 
int merge(int a,int b,int id){
    tree[id]=max(a,max(b,suf[id*2]+pref[id*2+1]));
    sum[id]=sum[id*2]+sum[id*2+1];
    pref[id]=max(pref[id*2],sum[id*2]+pref[id*2+1]);
    suf[id]=max(suf[id*2+1],sum[id*2+1]+suf[id*2]);
    return tree[id];
}
 
void push(int l,int r,int id){
    if(tag[id]!=-1e18){
        int mid=l+r>>1;
        tree[id<<1]=(tag[id]>0?tag[id]*(mid-l+1):0);
        sum[id<<1]=tag[id]*(mid-l+1);
        pref[id<<1]=(tag[id]>0?tag[id]*(mid-l+1):0);
        suf[id<<1]=(tag[id]>0?tag[id]*(mid-l+1):0);
        tree[id<<1|1]=(tag[id]>0?tag[id]*(r-mid):0);
        sum[id<<1|1]=tag[id]*(r-mid);
        pref[id<<1|1]=(tag[id]>0?tag[id]*(r-mid):0);
        suf[id<<1|1]=(tag[id]>0?tag[id]*(r-mid):0);
        tag[id<<1]=tag[id];
        tag[id<<1|1]=tag[id];
        tag[id]=-1e18;
    }
}
 
void modify(int ql,int qr,int val,int l,int r,int id){
    if(l!=r) push(l,r,id);
    if(ql<=l&&qr>=r){
        tree[id]=(val>0?val*(r-l+1):0);
        sum[id]=val*(r-l+1);
        pref[id]=(val>0?val*(r-l+1):0);
        suf[id]=(val>0?val*(r-l+1):0);
        tag[id]=val;
        return;
    }
    int mid=l+r>>1;
    if(ql<=mid) modify(ql,qr,val,l,mid,id<<1);
    if(qr>mid) modify(ql,qr,val,mid+1,r,id<<1|1);
    tree[id]=merge(tree[id<<1],tree[id<<1|1],id);
}
 
int query(int ql,int qr,int l,int r,int id){
    if(l!=r) push(l,r,id);
    if(ql<=l&&qr>=r){
        return tree[id];
    }
    int mid=l+r>>1;
    if(qr<=mid) return query(ql,qr,l,mid,id<<1);
    if(ql>mid) return query(ql,qr,mid+1,r,id<<1|1);
    return merge(query(ql,qr,l,mid,id<<1),query(ql,qr,mid+1,r,id<<1|1),id);
}

2. Watching Firework is fun

for(int i=1;i<=m;++i){
    deque<int> dq;
    for(int j=1;j<=min(n,(t[i]-t[i-1])*d+1);++j) dq.push_back(j);
    for(int j=1;j<=n;++j){
        int sz=(t[i]-t[i-1])*d*2+1,s=j-(t[i]-t[i-1])*d,tail=j+(t[i]-t[i-1])*d;
        s=max(1LL,s),tail=min(n,tail);
        if(!dq.empty()&&dq.front()<s) dq.pop_front();
        dp[i][j]=dp[i-1][dq.front()]+b[i]-abs(a[i]-j);
        while(!dq.empty()&&tail+1<=n&&dp[i-1][dq.back()]<=dp[i-1][tail+1]) dq.pop_back();
        if(tail+1<=n) dq.push_back(tail+1);
    }
}