题解 P3863 【序列】

如果只有一个数,似乎就很好维护了。

维护每一个时刻这个数加上的值。查询某一段时间里大于某个值的时间数量。将时间分块就可以做了。

但如果是 \(n\) 个数呢?如果在线搞的话,似乎并不能很好的维护。那么离线下来,给询问排序,依次处理就好了。

那怎么处理区间修改操作呢?观察到如果在 \(t\) 时刻给 \([l,r]\) 加上 \(v\),会对处理 \([l,r]\) 中每一个数时都造成同样的影响。所以将每一个修改操作分成两部分:

  • 第一部分,在处理第 \(l\) 个数的时候将时刻 \([t,m]\) 都加上 \(v\)
  • 第二部分,在处理第 \(r+1\) 个数的时候将时刻 \([t,m]\) 都减去 \(v\),抵消影响(因为这个操作不会对 \(r+1\) 及其之后的数造成影响,故减去)。

(是不是感觉有点像扫描线呢)

这样我们就可以得到每一个数每个时刻被加上的值。

处理第 \(i\) 个数第 \(t\) 秒的询问时,分块查询 \([0,t-1]\) 有多少个时刻大于等于 \(y - a_i\) 即可。

注意到最后输出结果时是按照输入顺序输出,所以还要处理一下询问的顺序。

# include <bits/stdc++.h>
# define rr register
# define int long long
const int N=100010;
struct Line{//修改
	int x;
	int Time;
	int v;
}a[N<<1];
struct Asker{//查询
	int x,v; 
	int Time;
	int Index;// 记录是第几次询问
}ask[N];
int cnta,cntb;//修改数量 & 查询数量
int ans[N]; // 存储每一次询问的答案
int val[N];
int n,m;
/* 分块部分 */
int tseque[N];
int fseque[N];
int add[N];
int Kuai[N];
int KL[N],KR[N];
/* 分块部分 */
int siz;// 要分的块大小
inline int read(void){
	int res,f=1;
	char c;
	while((c=getchar())<'0'||c>'9')
		if(c=='-')f=-1;
	res=c-48;
	while((c=getchar())>='0'&&c<='9')	
		res=res*10+c-48;
	return res*f;		
}
inline bool cmp_Line(Line X,Line Y){//给修改排序
	return X.x!=Y.x?X.x<Y.x:X.Time<Y.Time;
}
inline bool cmp_Ask(Asker X,Asker Y){//给询问排序
	return X.x!=Y.x?X.x<Y.x:X.Time<Y.Time;
}
inline bool cmp_Integer(int X,int Y){//为了给块内元素从大到小排序用的
	return X>Y;
}
inline void resort(int x){//每次修改之后,块内元素需要重新排序
	for(rr int i=KL[x];i<=KR[x];++i)
		fseque[i]=tseque[i];
	std::sort(fseque+KL[x],fseque+KR[x]+1,cmp_Integer);
	return;	
}
inline void change(int l,int r,int v){// 分块修改操作
	l=std::max(l,0ll);
	r=std::min(r,m);
	if(Kuai[l]==Kuai[r]){
		for(rr int i=l;i<=r;++i){
			tseque[i]+=v;
		}
		resort(Kuai[l]);
		return;
	}
	for(rr int i=l;i<=KR[Kuai[l]];++i)
		tseque[i]+=v;
	resort(Kuai[l]);
	for(rr int i=r;i>=KL[Kuai[r]];--i)
		tseque[i]+=v;
	resort(Kuai[r]);
	for(rr int i=Kuai[l]+1;i<=Kuai[r]-1;++i){
		add[i]+=v;
	}
	return;
}
inline int query(int l,int r,int v){// 分块查询操作
	int cnt=0;
	if(Kuai[l]==Kuai[r]){
		for(rr int i=l;i<=r;++i)
			if(tseque[i]+add[Kuai[i]]>=v)
				++cnt;
		return cnt;		
	}
	for(rr int i=l;i<=KR[Kuai[l]];++i)
		if(tseque[i]+add[Kuai[i]]>=v)
			++cnt;
	for(rr int i=r;i>=KL[Kuai[r]];--i)
		if(tseque[i]+add[Kuai[i]]>=v)
			++cnt;
	for(rr int i=Kuai[l]+1;i<=Kuai[r]-1;++i){
		int L=KL[i],R=KR[i],ans=KL[i]-1;
		while(L<=R){
			int mid=(L+R)>>1;
			if(fseque[mid]+add[Kuai[mid]]>=v){
				ans=mid;
				L=mid+1;
			}else{
				R=mid-1;
			}
		}
		cnt+=(ans-KL[i])+1;
	}
	return cnt;
}
# undef int
int main(void){
# define int long long
	n=read(),m=read();
	for(rr int i=1;i<=n;++i){
		val[i]=read();
	}
	for(rr int i=1,opt;i<=m;++i){
		opt=read();
		if(opt==1){
			int l=read(),r=read(),v=read();
			a[++cnta].x=l;
			a[cnta].Time=i;
			a[cnta].v=v;
			a[++cnta].x=r+1;
			a[cnta].Time=i;
			a[cnta].v=-v;
		}else{
			int p=read(),y=read();
			ask[++cntb].x=p;
			ask[cntb].Index=cntb;
			ask[cntb].v=y;
			ask[cntb].Time=i;
		}
	}
	std::sort(a+1,a+1+cnta,cmp_Line);
	std::sort(ask+1,ask+1+cntb,cmp_Ask);// 读入、存储并排序每一个操作
	siz=sqrt(m);
	for(rr int i=0;i<=m;++i){
		Kuai[i]=i/siz+1;
	}
	for(rr int i=1;(i-1)*siz<=m;++i){
		KL[i]=(i-1)*siz;
		KR[i]=std::min(i*siz-1,m);
	}
	int now=1;
	for(rr int i=1;i<=cntb;++i){
		while((a[now].x<ask[i].x||(a[now].x==ask[i].x&&a[now].Time<ask[i].Time))&&now<=cnta){
			change(a[now].Time,m,a[now].v);
			++now;
		}
		ans[ask[i].Index]=query(0,ask[i].Time-1,ask[i].v-val[ask[i].x]);
	}
	for(rr int i=1;i<=cntb;++i)
		printf("%lld\n",ans[i]);
	return 0;
} 
全部评论

相关推荐

码农索隆:单休一个月少休息4天,一年就是48天,平时节假日,别人3天假期,单休的两天
点赞 评论 收藏
分享
避坑恶心到我了大家好,今天我想跟大家聊聊我在成都千子成智能科技有限公司(以下简称千子成)的求职经历,希望能给大家一些参考。千子成的母公司是“同创主悦”,主要经营各种产品,比如菜刀、POS机、电话卡等等。听起来是不是有点像地推销售公司?没错,就是那种类型的公司。我当时刚毕业,急需一份临时工作,所以在BOSS上看到了千子成的招聘信息。他们承诺无责底薪5000元,还包住宿,这吸引了我。面试的时候,HR也说了同样的话,感觉挺靠谱的。于是,我满怀期待地等待结果。结果出来后,我通过了面试,第二天就收到了试岗通知。试岗的内容就是地推销售,公司划定一个区域,然后你就得见人就问,问店铺、问路人,一直问到他们有意向为止。如果他们有兴趣,你就得摇同事帮忙推动,促进成交。说说一天的工作安排吧。工作时间是从早上8:30到晚上18:30。早上7点有人叫你起床,收拾后去公司,然后唱歌跳舞(销售公司都这样),7:55早课(类似宣誓),8:05同事间联系销售话术,8:15分享销售技巧,8:30经理训话。9:20左右从公司下市场,公交、地铁、自行车自费。到了市场大概10点左右,开始地推工作。中午吃饭时间大约是12:00,公司附近的路边盖饭面馆店自费AA,吃饭时间大约40分钟左右。吃完饭后继续地推工作,没有所谓的固定中午午休时间。下午6点下班后返回公司,不能直接下班,需要与同事交流话术,经理讲话洗脑。正常情况下9点下班。整个上班的一天中,早上到公司就是站着的,到晚上下班前都是站着。每天步数2万步以上。公司员工没有自己的工位,百来号人挤在一个20平方米的空间里听经理洗脑。白天就在市场上奔波,公司的投入成本几乎只有租金和工资,没有中央空调。早上2小时,晚上加班2小时,纯蒸桑拿。没有任何福利,节假日也没有3倍工资之类的。偶尔会有冲的酸梅汤和西瓜什么的。公司的晋升路径也很有意思:新人—组长—领队—主管—副经理—经理。要求是业绩和团队人数,类似传销模式,把人留下来。新人不能加微信、不能吐槽公司、不能有负面情绪、不能谈恋爱、不能说累。在公司没有任何坐的地方,不能依墙而坐。早上吃早饭在公司外面的安全通道,未到上班时间还会让你吃快些不能磨蹭。总之就是想榨干你。复试的时候,带你的师傅会给你营造一个钱多事少离家近的工作氛围,吹嘘工资有多高、还能吹自己毕业于好大学。然后让你早点来公司、无偿加班、抓住你可能不会走的心思进一步压榨你。总之,大家在找工作的时候一定要擦亮眼睛,避免踩坑!———来自网友
qq乃乃好喝到咩噗茶:不要做没有专业门槛的工作
点赞 评论 收藏
分享
鬼迹人途:你去投一投尚游游戏,服务器一面,第一个图算法,做完了给你一个策略题,你给出方案他就提出低概率问题,答不上当场给你挂
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务