ZRX的美剧

【问题描述】

   猪所周知，ZRX是一个非常喜欢看美剧的小朋友，一天他搜自己喜欢的美剧，闪电侠第1季第3集，却找到了闪电侠的第3季第1集，他就产生了一个疑问，对于每一季x, 存在多少个y，（x<y),使得同时存在第x季第y集，第y季第x集。Zrx想让你从1到n输出这些答案，可是又由于某些审查的原因，在你输出完第i季的答案的时候，第l到第r季的美剧集数会减少di集，为了方便假设前面的答案不受影响，但是后面再要输出的答案会受到影响。

【数据范围】

        50% n<=1000

        100% n<=100000        

   对于所有数据有30%的数据d[i]=0

        d[i]<=65536

        首先我们可以先从小数据进行分析，有30%的数据d[i]=0，那么意味着没有减法，那问题第x次问的就是有多少个y是大于x的，（x<y),第一次询问的就是2~n有多少个大于等于1，第二次询问3~n有多少个大于等于2，以此类推，如果想到了这一步，主席树可以解决。可是如果要带修改的话，我们就要写带修主席树了，这样太麻烦了，而且事实上带修主席树并不支持区间修改，我们得使用更复杂的数据结构。

        我们来换种方法思考，那我们如果在每次询问之后给整个数组减一，那么每次询问的就是一部分数组大于等于一的数字的个数，这样的话，我们很容易发现，由于每一个数字只会减小，不会增多，所以从大于等于1变到小于1只会发生一次，所以我们可以最开始将所有位置对答案的贡献设置为1，每次给整个数组和普通线段树一样区间减1，如果发现当前最小值小于0了，那么我们就暴力的把它找到，并把它对答案的贡献改成0，把它改成无穷大，这样就能保证每个数字只会被暴力改一次了。如果带修改只需要把修改一起和上面的方法一样，给对应区间减一即可。

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#define maxn 200005
#define lson (now<<1)
#define rson ((now<<1)|1)
#define mid ((nl+nr)>>1)
using namespace std;
typedef long long ll;
ll n;
ll a[maxn];
ll minn[maxn<<2],dat[maxn<<2],lazy[maxn<<2];
void pushup(ll now)
{
 minn[now]=min(minn[lson],minn[rson]);
 dat[now]=dat[lson]+dat[rson];
}
void build(ll nl,ll nr,ll now)
{
 if(nl==nr)
 {
  minn[now]=a[nl];
  dat[now]=1;
  return;
 }
 build(nl,mid,lson);
 build(mid+1,nr,rson);
 pushup(now);
}
void pushdown(ll now)
{
 if(lazy[now])
 {
  minn[lson]+=lazy[now];
  minn[rson]+=lazy[now];
  lazy[lson]+=lazy[now];
  lazy[rson]+=lazy[now];
  lazy[now]=0;
 }
}
void check(ll nl,ll nr,ll ql,ll qr,ll now)
{
 if(nl==nr)
 {
  dat[now]=0;
  minn[now]=123456789123ll;
  return;
 }
 pushdown(now);
 if(minn[lson]<=0) check(nl,mid,ql,qr,lson);
 if(minn[rson]<=0) check(mid+1,nr,ql,qr,rson);
 pushup(now);
}
void update(ll nl,ll nr,ll d,ll ql,ll qr,ll now)
{
 if(ql<=nl && nr<=qr)
 {
  minn[now]+=d;
  lazy[now]+=d;
  if(minn[now]<=0)
  check(nl,nr,ql,qr,now);
  return;
 }
 pushdown(now);
 if(ql<=mid) update(nl,mid,d,ql,qr,lson);
 if(mid<qr) update(mid+1,nr,d,ql,qr,rson);
 pushup(now);
}
ll query(ll ql,ll qr,ll nl,ll nr,ll now)
{
 if(ql<=nl && nr<=qr)
  return dat[now];
 pushdown(now);
 ll ans=0;
 if(ql<=mid) ans+=query(ql,qr,nl,mid,lson);
 if(mid<qr) ans+=query(ql,qr,mid+1,nr,rson);
 pushup(now);
 return ans;
}
ll querypos(int ql,int nl,int nr,int now)
{
 if(nl==nr)
 return now;
 pushdown(now);
 if(ql<=mid) return querypos(ql,nl,mid,lson);
 else return querypos(ql,mid+1,nr,rson);
}
ll querya(int ql,int nl,int nr,int now)
{
 if(nl==nr)
 return minn[now];
 pushdown(now);
 if(ql<=mid) return querya(ql,nl,mid,lson);
 else return querya(ql,mid+1,nr,rson);
}
char s1[10005]="drama.in",s2[10005]="drama.out";
int main()
{
 freopen(s1,"r",stdin);
 freopen(s2,"w",stdout);
 scanf("%lld",&n);
 for(ll i=1;i<=n;i++)
 {
  scanf("%lld",&a[i]);
 }
 build(1,n,1);
 ll ans=0;
 for(ll i=1;i<=n;i++)
 {
  ll pos=querypos(i,1,n,1);
  if(dat[pos]!=0)
  {
   ll temp=query(i+1,min(n,querya(i,1,n,1)+i-1),1,n,1);
   printf("%lld\n",temp);
   ans+=temp;
  }
  else
  printf("0\n");
  update(1,n,-1,1,n,1);
  ll ll,rr,xx;
  scanf("%lld%lld%lld",&ll,&rr,&xx);
  update(1,n,-xx,ll,rr,1);
 }
}

原文出处