线段树

专题

#include<iostream>
#include<cstdio>
using namespace std;
typedef long long ll;
#define N 50005
ll num[N];
ll sum[N<<2];
ll tree[N<<2];
char s[10];
int a,b,n;

void PushUp(int rt){

tree[rt]=tree[rt<<1]+tree[rt<<1|1];

}
void build(int l,int r,int rt){
if(l==r){
    tree[rt]=num[l];
    return;
}
int mid=(l+r)>>1;
build(l,mid,rt<<1);
build(mid+1,r,rt<<1|1);
PushUp(rt);
}

void update(int L,ll c,int l,int r,int rt){

if(l==r)
{

    tree[rt]+=c;
    return;
}
int mid=(l+r)>>1;
if(L<=mid){
    update(L,c,l,mid,rt<<1);
}else{
   update(L,c,mid+1,r,rt<<1|1);
}
PushUp(rt);
}

ll query(int L,int R,int l,int r,int rt){

ll ans=0;
if(L<=l&&R>=r){

return  tree[rt];

}
int mid=(r+l)>>1;
if(L<=mid){
    ans+=query(L,R,l,mid,rt<<1);
}
if(R>=mid+1){
    ans+=query(L,R,mid+1,r,rt<<1|1);
}

return ans;

}
int main()
{
    int T;
    scanf("%d",&T);

    for(int cas=1;cas<=T;cas++){
        printf("Case %d:\n",cas);
        scanf("%d",&n);
        for(int i=1;i<=n;i++){
            scanf("%lld",&num[i]);
        }
         build(1,n,1);

         
        while(1){
            scanf("%s",&s);
            if(s[0]=='Q'){
                scanf("%d%d",&a,&b);
                printf("%lld\n",query(a,b,1,n,1));
            }else if(s[0]=='S'){ ll x; scanf("%d%lld",&a,&x);
                update(a,-x,1,n,1);
            }else if(s[0]=='A'){
                ll x; scanf("%d%lld",&a,&x);
                update(a,x,1,n,1);
            }else{
                break;
            }
        }
    }
    return 0;
}

B
线段树求逆序对

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
typedef long long ll;
#define N 10005
ll a[N];
ll tree[N<<2];
int n;
void PushUp(int rt){
    tree[rt]=tree[rt<<1]+tree[rt<<1|1];
}
void build(int l,int r,int rt){
if(l==r){
    tree[rt]=0;return;
}
int m=(l+r)>>1;
build(l,m,rt<<1);
build(m+1,r,rt<<1|1);
PushUp(rt);
}
void updata(int L,int c,int l,int r,int rt){
if(l>r)
    return ;
if(l==r){
    tree[rt]++;
    return;
}
int m=(l+r)>>1;
if(L<=m) updata(L,c,l,m,rt<<1);
else  updata(L,c,m+1,r,rt<<1|1);

PushUp(rt);
}
ll query(int L,int R,int l,int r,int rt){

if(L>R)
    return 0;
if(L<=l&&R>=r){
    return tree[rt];
}
ll ans=0;
int m=(r+l)>>1;
if(L<=m) ans+=query(L,R,l,m,rt<<1);
if(R>m) ans+=query(L,R,m+1,r,rt<<1|1);
return ans;
}
ll ans[N];
ll mm[N];
int main()
{

    while(~scanf("%d",&n)){
        memset(tree,0,sizeof(tree));
        for(int i=1;i<=n;i++){
            scanf("%lld",&a[i]);
            a[i]++;
            a[i+n]=a[i];
        }
        int tn=n;
        n=2*n-1;
       for(int i=1;i<=tn;i++){
           updata(a[i],1,1,n,1);
           mm[i]=query(1,a[i]-1,1,n,1);
           ans[i]=ans[i-1]+i-1-mm[i];
        }

        ll temp=ans[tn];
        ll an=temp;
        for(int i=1;i<tn;i++){
            an=min(temp-(a[i]-1)+tn-a[i],an);
            temp=temp-(a[i]-1)+tn-a[i];
        }
         printf("%lld\n",an);
        }
    return 0;
}

C[]

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
typedef long long ll;
#define N 50005
#define mod 1000000007
ll ni;
int a,b,c;
int n,q;

ll tree[N<<2];
ll num[N];

void PushUp(int rt){
tree[rt]=tree[rt<<1]*tree[rt<<1|1];
tree[rt]%=mod;
}
void build(int l,int r,int rt){
    if(l==r){
        tree[rt]=num[l];
        return;
    }
    int m=(l+r)>>1;
    build(l,m,rt<<1);
    build(m+1,r,rt<<1|1);
    PushUp(rt);
}
ll update(int L,ll c,int l,int r,int rt){

if(l==r){
    tree[rt]=c;
    return tree[rt];
}
int m=(r+l)>>1;
if(L<=m) update(L,c,l,m,rt<<1);
 else update(L,c,m+1,r,rt<<1|1);
PushUp(rt);
}

ll query(int L,int R,int l,int r,int rt){

if(L<=l&&R>=r){

    return tree[rt];
}
ll ans=1;
int m=(l+r)>>1;
if(L<=m){
    ans*=query(L,R,l,m,rt<<1);
    ans%=mod;
}
if(R>m)
{
    ans*=query(L,R,m+1,r,rt<<1|1);
    ans%=mod;
}

return ans;

}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--){
    memset(tree,1,sizeof(tree));
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%lld",&num[i]);
    }

    build(1,n,1);
    scanf("%d",&q);
    for(int i=0;i<q;i++){
        scanf("%d",&c);
        ll x;
        if(c==0){
                scanf("%d%d",&a,&b);
        printf("%lld\n",query(a,b,1,n,1));
        }else{
          scanf("%d%lld",&a,&x);
           update(a,x,1,n,1);
        }
    }
    
    }
    return 0;
}
/*
0  1 2
0  1 3
0  1 4
0  2 7

1  2 1
1  3 1

0  1 2
0  1 3
0  1 4
0  2 7
*/

D 区间不同值求和