我的天——神奇的贡献转换

description

今有(n)人,互不认识,排成一列.现有(m)轮操作,每轮操作给出区间([l,r]),使区间内互不认识的人相认识.试问每轮操作可以新产生多少对相互认识的人?

solution

考场上只想出了(10)pts的暴力分,一一枚举,复杂度(Omicron(mcdot n^{2})).现给出(50)pts解法:

我们可以开一个数组(f),(f[i])表示第(i)个人向右所能认识的最远的人,故每次计算改为计算贡献,然后更新(f[i]).又由于(f[i])显然具有单调性,于是我们可以开线段树维护,复杂度(Omicron(mlog n))

code

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#include<map>
#include<set>
#define R register
#define next kdjadskfj
#define debug puts("mlg")
#define mod 1000000000
#define Mod(x) ((x%mod+mod)%mod)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
inline ll read();
inline void write(ll x);
inline void writeln(ll x);
inline void writesp(ll x);
const ll maxn=600000;
ll n,m;
ll dat1[maxn<<2],dat2[maxn<<2],sum[maxn<<2];
ll lazy[maxn<<2];
inline void build(ll p,ll l,ll r){
	if(l==r){dat1[p]=dat2[p]=sum[p]=l;return;}
	ll mid=l+r>>1;
	build(p<<1,l,mid);build(p<<1|1,mid+1,r);
	dat1[p]=min(dat1[p<<1],dat1[p<<1|1]);
	dat2[p]=max(dat2[p<<1],dat2[p<<1|1]);
	sum[p]=sum[p<<1]+sum[p<<1|1];
}
inline void pushdown(ll p,ll l,ll r){
	if(lazy[p]){
		dat1[p<<1]=dat1[p<<1|1]=dat2[p<<1]=dat2[p<<1|1]=lazy[p];
		ll mid=l+r>>1;
		sum[p<<1]=(lazy[p]*(mid-l+1));
		sum[p<<1|1]=lazy[p]*(r-mid);
		lazy[p<<1]=lazy[p];lazy[p<<1|1]=lazy[p];
		lazy[p]=0;
	}
}
ll ansr;
inline ll query(ll p,ll l,ll r,ll u,ll v){
	pushdown(p,l,r);
	if(u<=l&&r<=v&&dat2[p]<v){
		ansr=max(ansr,r);
		return v*(r-l+1)-sum[p];
	}
	ll mid=l+r>>1,Sum=0;
	if(u<=mid&&dat1[p<<1]<v) Sum+=query(p<<1,l,mid,u,v);
	if(v>mid&&dat1[p<<1|1]<v) Sum+=query(p<<1|1,mid+1,r,u,v);
	return Sum;
}
inline void update(ll p,ll l,ll r,ll u,ll v,ll k){
	if(u<=l&&r<=v){
		dat1[p]=dat2[p]=k;
		sum[p]=(r-l+1)*k;
		lazy[p]=k;
		return;	
	}
	ll mid=l+r>>1;
	if(u<=mid) update(p<<1,l,mid,u,v,k);
	if(v>mid) update(p<<1|1,mid+1,r,u,v,k);
	dat1[p]=min(dat1[p<<1],dat1[p<<1|1]);
	dat2[p]=max(dat2[p<<1],dat2[p<<1|1]);
	sum[p]=sum[p<<1]+sum[p<<1|1];
}
int main(){	
	freopen("ohmygod.in","r",stdin);
	freopen("ohmygod.out","w",stdout);
	n=read();m=read();
	build(1,1,n);
	while(m--){
		ansr=0;
		ll l=read(),r=read();
		ll ans=query(1,1,n,l,r);
		writeln(ans);
		if(ansr){
			update(1,1,n,l,ansr,r);
		}
	}
}
inline ll read(){ll x=0,t=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-') t=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*t;}
inline void write(ll x){if(x<0){putchar('-');x=-x;}if(x<=9){putchar(x+'0');return;}write(x/10);putchar(x%10+'0');}
inline void writesp(ll x){write(x);putchar(' ');}
inline void writeln(ll x){write(x);putchar('
');}