练习情况

P2184 贪婪大陆

每次埋不同的地雷，对于每次询问考虑在 \(l\) 之前有多少次埋地雷， \(r\) 之后埋多少次地雷

然后用总次数减去得到答案

Code:

#include<bits/stdc++.h>
using namespace std;
#define LL long long
const int N = 100005;
LL n,m,opt,l,r,tot,a1,a2;
struct node{
    LL c[N];
    LL lowbit(LL x){return x&-x;}
    void add(LL p){while(p<=n){c[p]+=1;p+=lowbit(p);}return ;}
    LL sum(LL p){LL ans=0;while(p){ans+=c[p],p-=lowbit(p);}return ans;}
}t1,t2;
int main(){
    cin>>n>>m;
    while(m--){
        cin>>opt>>l>>r;
        if(opt==1)t1.add(r),t2.add(l),tot++;
        else a1=t1.sum(l-1),a2=t2.sum(n)-t2.sum(r),cout<<tot-a1-a2<<"\n";
    }
}

P2122 还教室

P5142 区间方差

将方差公式拆分

用线段树维护区间和，区间平方和。

Code:

线段树

树状数组

#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define Ld long double
const int N = 100005;

LL n,m,mod=1e9+7,op,x,y;
LL a[N],k;
struct node{
    LL c[N];
    LL lowbit(LL x){return x&-x;}
    void add(LL p,LL k){while(p<=n){c[p]=(c[p]+k+mod)%mod;p+=lowbit(p);}return ;}
    LL sum(LL p){LL ans=0;while(p){ans=(ans+c[p]+mod)%mod,p-=lowbit(p);}return ans;}
}t1,t2;

LL ksm(LL a,LL b){
    LL res=1;
    while(b){
        if(b&1)
        res=(res*a)%mod;
        a=(a*a)%mod;b>>=1;
    }
    return res;
}

int main(){
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%lld",&a[i]);
        t1.add(i,(a[i]%mod)),t2.add(i,((a[i]*a[i])%mod));
    }
    for(int i=1;i<=m;i++){
        scanf("%lld%lld%lld",&op,&x,&y);
        if(op==1){
            t1.add(x,-(a[x]%mod)),t2.add(x,-((a[x]*a[x])%mod));
            t1.add(x,(y%mod)),t2.add(x,((y*y)%mod));
            a[x]=y;
        }
        else{
            LL sum=t1.sum(y)-t1.sum(x-1);
            LL sum2=t2.sum(y)-t2.sum(x-1);
            LL inv=ksm(y-x+1,mod-2);
            LL ave=sum*inv%mod;
            LL ans=sum2*inv%mod-ave*ave%mod;
            ans=(ans%mod+mod)%mod;
            printf("%lld\n",ans);
        }
    }
    return 0;
}

P1533 可怜的狗狗

权值线段树/树状数组

区间 \([l,r]\) 不互相包含

故离线将其按右端点排序，用两指针维护序列 (参考莫队维护)，再二分

记得离散化

Code:

#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define Ld long double
const int N = 300005,M=20005;

LL n,m,a[N],val[N],ans[N],lv;
struct node{
    LL l,r,k,id;
}t[N];
struct node1{
    LL c[N];
    inline void add(LL p,LL k){while(p<=lv){c[p]+=k;p+=(p&-p);}return ;}
    inline LL sum(LL p){LL ans=0;while(p){ans+=c[p],p-=(p&-p);}return ans;}
}t1;

bool cmp(node a, node b){
    return a.r<b.r;
}

int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        val[i]=a[i];
    }
    sort(val+1,val+1+n);
    lv=unique(val+1,val+1+n)-val-1;
    for(int i=1;i<=m;i++){
        cin>>t[i].l>>t[i].r>>t[i].k;
        t[i].id=i;
    }
    sort(t+1,t+1+m,cmp);
    LL l=1,r=1,pos;
    for(int i=1;i<=m;i++){
        for(int j=r;j<=t[i].r;j++)
        pos=lower_bound(val+1,val+1+lv,a[j])-val,t1.add(pos,1);
        for(int j=l;j<t[i].l;j++)
        pos=lower_bound(val+1,val+1+lv,a[j])-val,t1.add(pos,-1);
        r=t[i].r+1;
        l=t[i].l;
        LL ll=1,rr=lv;
        while(ll<rr){
            LL mid=(ll+rr)>>1;
            if(t1.sum(mid)<t[i].k)
                ll=mid+1;
            else rr=mid;
        }
        ans[t[i].id]=ll;
    }
    for(int i=1;i<=m;i++){
        printf("%lld\n",val[ans[i]]);
    }
	return 0;
}

P2061 [USACO07OPEN]City Horizon S

傻逼题，等我完全搞懂再写