hgoi#20191107

muronglin
muronglin 2019年11月07日
  • 在其它设备中阅读本文章

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("%dn",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;
}