[数据结构与算法]Codeforces 1457 E. Air Conditioners

Codeforces 1457 E. Air Conditioners

题意

有n个格子，k个格子里有空调。，每个空调有度数。
对于任意一个格子$i$,它的温度等于所有有空调格子的温度加上它距离$i$格子之间的距离的最小值
求所有格子的温度

题解

对于第一个格子，我们可以算出每个空调对它的影响的温度，那这个格子的温度即为这些值中的最小值，
那么对于第二个格子怎么办？
就是把第2个格子前面的空调温度影响+1.后面的空调温度影响-1，怎么维护？
简单的极值线段树

标程

#include<bits/stdc++.h>
using namespace std;
const int MAXN=3e5+7;
typedef long long ll;
const ll inf=0x3f3f3f3f3f3f3f3f;
ll a[MAXN],sum[MAXN*4],flag[MAXN*4];
int n,m,k,q;
struct node{
	ll a,t;
	bool operator <(const node & p) const{
		return a<p.a;
	}
}e[MAXN];
inline void pushup(int rt){
	sum[rt]=min(sum[rt*2],sum[rt*2+1]);
}
inline void Build(int l,int r,int rt){
	flag[rt]=0;
	if(l==r){
		sum[rt]=e[l].t+abs(1-e[l].a); return;
	}
	int mid=(l+r)/2;
	Build(l,mid,rt*2);
	Build(mid+1,r,rt*2+1);
	pushup(rt);
}
inline void pushdown(int l,int r,int rt){
	if(flag[rt]!=0){
		int mid=(l+r)/2;
		flag[rt*2]+=flag[rt];
		flag[rt*2+1]+=flag[rt];
		sum[rt*2]+=flag[rt];
		sum[rt*2+1]+=flag[rt];
		flag[rt]=0;
	}
}
inline void add_qj(int l,int r,int L,int R,int rt,int k){
	if(L<=l&&r<=R){
		sum[rt]+=k;
		flag[rt]+=k;
		return;
	}
	if(flag[rt]!=0) pushdown(l,r,rt);
	int mid=(l+r)/2;
	if(L<=mid) add_qj(l,mid,L,R,rt*2,k);
	if(R>mid) add_qj(mid+1,r,L,R,rt*2+1,k);
	pushup(rt);
}
inline void add_point(int l,int r,int d,int rt,int k){
	if(l==r){
		sum[rt]+=k;
		return;
	}
	if(flag[rt]!=0) pushdown(l,r,rt);
	int mid=(l+r)/2;
	if(d<=mid) add_point(l,mid,d,rt*2,k);
	if(d>mid) add_point(mid+1,r,d,rt*2+1,k);
	pushup(rt);
}
inline ll query_point(int l,int r,int d,int rt){
	ll ans=inf;
	if(l==r){
		return sum[rt];
	}
	pushdown(l,r,rt);
	int mid=(l+r)/2;
	if(d<=mid) ans=min(ans,query_point(l,mid,d,rt*2));
	if(d>mid) ans=min(ans,query_point(mid+1,r,d,rt*2+1));
	return ans;
}
inline ll query_qj(int l,int r,int L,int R,int rt){
	ll ans=inf;
	if(L<=l&&r<=R){
		return sum[rt];
	}
	pushdown(l,r,rt);
	int mid=(l+r)/2;
	if(L<=mid) ans=min(ans,query_qj(l,mid,L,R,rt*2));
	if(R>mid) ans=min(ans,query_qj(mid+1,r,L,R,rt*2+1));
	return ans;
}

int main(){
	scanf("%d",&q);
	while(q--){
		scanf("%d%d",&n,&k);
		for(int i=1;i<=k;i++) scanf("%lld",&e[i].a);
		for(int i=1;i<=k;i++) scanf("%lld",&e[i].t);
		sort(e+1,e+1+k);
		for(int i=1;i<=k;i++) a[i]=e[i].a;
		Build(1,k,1);
		int tmp=1;
		for(int i=1;i<=n;i++){
			printf("%lld ",sum[1]);
			if(i>=e[tmp].a&&tmp<=k){
				tmp++;
			}
			if(tmp>1) add_qj(1,k,1,tmp-1,1,1);
			if(tmp<=k) add_qj(1,k,tmp,k,1,-1);
		}
	}
}