慕容琳的后花园
慕容琳的后花园
hgoi#20191107

T2-雇佣妹抖

给定一个长度为 n 的数组 A,有两种操作:
1.修改 A_x=y
2.查询 A 中所有大于等于 x 的数能构成几段连续的区间

解法

我们可以发现所有大于等于 x 的数能构成连续区间的段数
等于大于等于 x 的数的个数减去相邻两个数都大于等于 x 的位置的对数
那么我们维护两个树状数组,一个维护所有数,一个维护相邻两个数的最小值
询问时查询两个后缀和即可

ac代码

#include<bits/stdc++.h>
#define N 200010
using namespace std;
int n,m,cnt,a[N],tmp[N<<1],cnta[N<<1],cntb[N<<1];
struct opt{int t,x,y;}b[N];
void add(int *A,int x,int v){for(x=cnt+1-x;x<=cnt;x+=(x&(-x)))A[x]+=v;}
int ask(int *A,int x){int ans=0;for(x=cnt+1-x;x;x-=(x&(-x)))ans+=A[x];return ans;}
void ins(int x,int v){add(cnta,a[x],v);if(x>1)add(cntb,min(a[x-1],a[x]),v);if(x<n)add(cntb,min(a[x],a[x+1]),v);}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]),tmp[++cnt]=a[i];
    for(int i=1;i<=m;i++)
    {
        scanf("%d",&b[i].t);
        if(b[i].t==1)scanf("%d",&b[i].x),tmp[++cnt]=b[i].x;
        else scanf("%d%d",&b[i].x,&b[i].y),tmp[++cnt]=b[i].y;
    }
    sort(tmp+1,tmp+1+cnt),cnt=unique(tmp+1,tmp+1+cnt)-tmp-1;
    for(int i=1;i<=n;i++)a[i]=lower_bound(tmp+1,tmp+1+cnt,a[i])-tmp;
    for(int i=1;i<=m;i++)
        if(b[i].t==1)b[i].x=lower_bound(tmp+1,tmp+1+cnt,b[i].x)-tmp;
        else b[i].y=lower_bound(tmp+1,tmp+1+cnt,b[i].y)-tmp;
    for(int i=1;i<=n;i++)add(cnta,a[i],1);
    for(int i=1;i<n;i++)add(cntb,min(a[i],a[i+1]),1);
    for(int i=1;i<=m;i++)
        if(b[i].t==1)printf("%d\n",ask(cnta,b[i].x)-ask(cntb,b[i].x));
        else ins(b[i].x,-1),a[b[i].x]=b[i].y,ins(b[i].x,1);
    return 0;
}
赞赏
https://secure.gravatar.com/avatar/8cbc0c58deea66b18e9a96cd4bdd6eea?s=256&d=monsterid&r=g

慕容琳

文章作者

发表评论

textsms
account_circle
email

慕容琳的后花园

hgoi#20191107
T2-雇佣妹抖 给定一个长度为 $n$ 的数组 $A$,有两种操作: 1.修改 $A_x=y$ 2.查询 $A$ 中所有大于等于 $x$ 的数能构成几段连续的区间 解法 我们可以发现所有大于等于 $x$ 的数能构成…
扫描二维码继续阅读
2019-11-07
功能