8-4作业/重写ren_gao_zu

ren_gao_zu · 2025-08-05 10:10:51 · 个人记录

作业

P10589 楼兰图腾

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N=5e5+5;
int c[N],n,m,s1,s2,a[N];
int lowbit(int x){
    return x & -x;
}
int get_sum(int x){
    int res=0;
    while(x){
        res+=c[x];
        x-=lowbit(x);
    }
    return res;
}
void modify(int x,int val){
    while(x<=n){
        c[x]+=val;
        x+=lowbit(x);
    }
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=n;i++){
        int l=get_sum(a[i]-1),r=i-1-l;
        s1+=l*(a[i]-1-l);
        s2+=r*(n-a[i]-r);
        modify(a[i],1);
    }
    cout<<s2<<" "<<s1;

    return 0;
}

P3372 【模板】线段树 1

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N=1e6+5;
int c1[N],c2[N],n,m,a[N];
int lowbit(int x){
    return x & -x;
}
int get_sum(int x,int c[]){
    int res=0;
    while(x){
        res+=c[x];
        x-=lowbit(x);
    }return res;
}
void modify(int x,int val,int c[]){
    while(x<=n){
        c[x]+=val;
        x+=lowbit(x);
    }
}
int d[N];
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        d[i]=a[i]-a[i-1];
    }
    for(int i=1;i<=n;i++){
        modify(i,d[i],c1);
        modify(i,(i-1)*d[i],c2);
    }
    while(m--){
        int op,x,y,k;
        cin>>op>>x;
        if(op==1){
            cin>>y>>k;
            modify(x,k,c1);modify(y+1,-k,c1);
            modify(x,k*(x-1),c2);
            modify(y+1,-k*y,c2);
        }
        else{
            cin>>y;
            int ans=(x-1)*get_sum(x-1,c1)-get_sum(x-1,c2);
            int top=y*get_sum(y,c1)-get_sum(y,c2);
            cout<<top-ans<<endl;
        }
    }
    return 0;
}

重写

P1198 [JSOI2008] 最大数

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N=5e5+5;
int n,m,D,sum[N];
int lowbit(int x){
    return x&-x;
}
void modify(int x,int k){
    while(x>=1){
        sum[x]=max(sum[x],k);
        x-=lowbit(x);
    }
    return;
}
int get_sum(int x)
{
    int res=-1e9;
    while(x<=n){
        res=max(res,sum[x]);
        x+=lowbit(x);
    }
    return res;
}
int pre;
signed main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cin>>m>>D;
    while(m--){
        char op;
        int x;
        cin>>op>>x;
        if(op=='A'){
            n++;
            x+=pre;
            modify(n,x%D);
        }
        else if(op=='Q'){
            int len=n-x+1;
            pre=get_sum(len);
            cout<<pre<<endl;
        }
    }
    return 0;
}