洛谷 P4587 [FJOI2016]神秘数(主席树,dp)

作者:神秘网友 发布时间:2021-10-13 07:24:03

洛谷 P4587 [FJOI2016]神秘数(主席树,dp)

传送门


解题思路

今晚csp报名网站炸了QAQ,发布新闻者禁三警告
先考虑暴力dp:
O(na)的想必大家都会,但一遍都做不下来。
所以需要换一种dp。
假设求序列[l……r]的答案。
先将其排序,假设到第i-1位时能表示出来的范围为[1..x],则只要判断第i位是否大于x+1即可。
若小于x+1,则范围扩大到x+a[i],向下循环即可。

然后用权值线段树维护区间和,变成主席树维护序列区间。

最后时间复杂度为 \(O(mlog^2a)\)

AC代码

#includeiostream
#includecstdio
#includecstring
#includecmath
#includealgorithm
#includevector
#includequeue
#includemap
using namespace std;
const int maxn=1e5+5;
const int maxx=1e9+5;
int n,m,cnt,rt[maxn];
long long a[maxn];
struct node{
	int ls,rs;
	long long  value;
}d[maxn*40];
void update(int x,int last,int l,int r,long long v){
	x=++cnt;
	d[x]=d[last];
	d[x].value+=v;
	if(l==r) return;
	int mid=(l+r)/2;
	if(v=mid) update(d[x].ls,d[last].ls,l,mid,v);
	else update(d[x].rs,d[last].rs,mid+1,r,v);
}
long long query(int x,int y,int l,int r,long long v){
	if(r=v){
		return d[y].value-d[x].value;
	}
	int mid=(l+r)/2;
	long long res=0;
	res+=query(d[x].ls,d[y].ls,l,mid,v);
	if(vmid) res+=query(d[x].rs,d[y].rs,mid+1,r,v);
	return res;
}
int main(){
	ios::sync_with_stdio(false);
	cinn;
	for(int i=1;i=n;i++){
		cina[i];
		update(rt[i],rt[i-1],1,maxx,a[i]);
	}
	cinm;
	for(int i=1;i=m;i++){
		int l,r;
		cinlr;
		long long ans=1; 
		while(1){
			long long res=query(rt[l-1],rt[r],1,maxx,ans);
			if(resans) break;
			ans=res+1;
		}
		coutansendl;
	}
	return 0;
}

本文章教程介绍完毕,更多请访问跳墙网其他文章教程!

洛谷 P4587 [FJOI2016]神秘数(主席树,dp) 相关文章

  1. 洛谷P4587 主席树+倍增

    首先考虑[l,r]的解决方法。 1,1,1,5,9,10,1 假设从[l,l+x]可以表达连续的从1-p的数字,那么如果l+x+1 比p大,那么从左往右会有断档 而如果l+x+1的值(a[l+x+1])比p小,这样就会1-p可行和1+a[l+x+1]---p+a[l+x+1])这两个区间是重复的,那么...

  2. #启发式合并,LIS,平衡树#洛谷 4577 [FJOI2018]领导集团问题

    题目 在一棵树上选择最多的点,使得存在祖先关系的点满足\(w_x\leq w_y\),其中\(x\)是\(y\)的祖先 分析 祖先链上要满足\(LIS\),考虑将子节点的LIS序列合并至节点\(x\), 用启发式合并就可以做到\(O(nlog^2n)\),同时还要将\(w_x\)插入, ...

  3. #主席树,fread,fwrite#洛谷 1972 [SDOI2009]HH的项链

    题目 分析 维护每个位置的后继,问题转换为后继在区间外的位置的个数, 但是这题太卡常了,所以我就加了fread和fwrite 其实树状数组的解法我也写过了 代码 #include cstdio#include cctype#include algorithm#define rr register#define getchar() (p1==p...

  4. #虚树,树形dp#洛谷 3233 [HNOI2014]世界树

    题目 分析 考虑建一棵虚树,倍增找到虚树上相邻两个点的中间点统计答案 记录每个虚树点最近的距离以及编号最小的点,主要是细节问题 代码 #include cstdio#include cctype#include algorithm #define rr registerusing namespace std;const int N=300011; s...

  5. #斯坦纳树,状压dp#洛谷 3264 [JLOI2015]管道连接

    题目 分析 如果对于每一个频道单独跑斯坦纳树可能会存在两种频道共用一条道路而重复统计的情况, 考虑状压dp,设\(f[s]\)表示选择频道二进制状态为\(s\)的最小贡献,那么对于每个状态跑斯坦纳树然后状压求最小值即可 代码 #...

  6. 洛谷$P2605\ [ZJOI2010]$基站选址 线段树优化$dp$

    洛谷$P2605\ [ZJOI2010]$基站选址 线段树优化$dp$ 传送门$QwQ$ 难受阿,,,本来想做考试题的,我还造了个精妙无比的题面,然后今天讲$dp$的时候被讲到了$kk$ 先考虑暴力$dp$?就设$f_{i,j}$表示选的第$j$个基站是$i$的最小费用,就有$f_{i,j}=min(f_{k,...

  7. P4585-[FJOI2015]火星商店问题【线段树,可持久化Trie】

    正题 题目链接:https://www.luogu.com.cn/problem/P4585 题目大意 \(n\)个集合,开始每个集合中有一个数字。 开启新的一天并且往集合\(s\)中插入数字\(v\) 询问\(d\)天以内插入的数字(包括最开始的)中\(l\sim r\)集合内的数字异或上\(x\)的最...

  8. 洛谷P1725(单调队列优化DP)

    洛谷P1725(单调队列优化DP) 链接 不难想出暴力解法,类比走楼梯,对于每个位置找出可以到达此处的前一个位置,然后暴力更新(肯定超时) 可以发现,对于每一个位置iii的解,我们都是在(i?R,i?Li-R,i-Li?R,i?L)种选取一个...

  9. 洛谷 P1002 过河卒 (二维DP)

    洛谷 P1002 过河卒 (二维DP) #includeiostream#includecstdio#includealgorithm#define MAXN 35using namespace std;typedef unsigned long long ull;int a,b,c,d;ull f[MAXN][MAXN];int s[MAXN][MAXN];int dx[9]={0,-2,-1,1,2,2,1,-1,-2};int dy[9]={0,1,2

  10. 洛谷 P1002 过河卒(dp)

    洛谷 P1002 过河卒(dp) P1002 过河卒 时间限制1.00s 内存限制125.00MB 棋盘上 AA 点有一个过河卒,需要走到目标 BB 点。卒行走的规则:可以向下、或者向右。同时在棋盘上 CC 点有一个对方的马,该马所在的点和所有跳跃一步可达的点...

  11. 【洛谷4983】忘情(WQS二分+斜率优化DP)

    点此看题面 给定一个长度为\(n\)的序列\(a\),要求你把它划分成\(m\)段。 令\(sum_i\)表示第\(i\)段的数之和,求\(\sum_{i=1}^m(sum_i+1)^2\)的最小值。 \(m\le n\le10^5\) \(WQS\)二分 一来这种套路早就见过了,二来事先知道了这题是\(WQS\)二分,...

  12. 洛谷 P1352 没有上司的舞会(树形 DP)

    洛谷 P1352 没有上司的舞会(树形 DP) 某大学有N个职员,编号为1~N。他们之间有从属关系,也就是说他们的关系就像一棵以校长为根的树,父结点就是子结点的直接上司。现在有个周年庆宴会,宴会每邀请来一个职员都会增加一定...

  13. 背包类树形DP-洛谷P2014 [CTSC1997]选课

    背包类树形DP-洛谷P2014 [CTSC1997]选课 背包类树形DP-洛谷P2014 [CTSC1997]选课 背包类树形DP 例题 思路 代码 注:本文章参考《算法竞赛 进阶指南》(李煜东2018年1月第一版P291~292),引用文本均摘自该书 背包类树形DP 又称树形有依赖的...

  14. 洛谷 P1352 没有上司的舞会(树形DP)

    题目链接 这是一道终极经典的树形DP的例题。 树形dp就是将DP的数据放到了一棵树上。每个父节点与其子节点的值有关。推出如何建树和递推公式即可。 f[i][j].(j=1/0)i表示这是谁,j为1时表示来,0时表示不来。这个式子表示i来...

  15. [THU2016] 洛谷 P6670 汽水

    题意是在有边权的树上寻找平均边权与 \(k\) 最接近的链。树上找链的问题可以考虑点分治,而点分治的 \(\mathtt{Solve()}\) 函数要处理过重心的链。 记 \(dis_x\) 为 \(x\) 到重心的边权和, \(dep_x\) 为 \(x\) 的深度,则链 \((x,y)\) 的平均...

  16. 洛谷数颜色

    洛谷数颜色 初见安~这里是传送门:洛谷P3939 数颜色 题解 题意很显然,操作交换相邻的两个兔子和求区间内某颜色兔子的个数。 区间条件+颜色条件,带修主席树可以一发带走。【可是我不会】 考虑每个询问只跟颜色有关,所...

  17. 可持久化线段树(主席树)

    为什么要叫主席树呢 听说发明人姓名首字母是hjt( 每次对线段树修改后将的修改后节点存入另一颗树中 树的其中一个孩子即之前的修改后节点 另一个孩子是原先的线段树 例题 P3834 【模板】可持久化线段树 2(主席树) 题目背...

  18. 洛谷P3311 [SDOI2014]数数 AC自动机+dp

    洛谷P3311 [SDOI2014]数数 AC自动机+dp 正解:AC自动机+dp 解题报告: 传送门! 首先看到多串匹配balabala显然想到建个AC自动机? 然后可以用一点儿数位dp的思想地想下(,,,其实并不算QAQ 幸运数可以分为两类:位数n的和位数=n的 下面分别考虑...

  19. 洛谷 P3600 - 随机数生成器(期望 dp)

    题面传送门 我竟然独立搞出了这道黑题!incredible! u1s1 这题是我做题时间跨度最大的题之一…… 首先讲下我四个月前想出来的 \(n^2\log n\) 的做法吧。 记 \(f(a)=\max\limits_{i=1}^q\min\limits_{j=l_i}^{r_i}a_j=x\) 首先期望转概率,设 \(p_i\) ...

  20. 洛谷:P5858 「SWTR-03」Golden Sword(dp,提高+/省选-)

    洛谷:P5858 「SWTR-03」Golden Sword(dp,提高+/省选-) #includebits/stdc++.husing namespace std;long long A[5505][5505];//dp int B[5505];// 原始数据 int m,w,s;// 原料总数 容纳max 取max int main(){ for(int i=0;i5505;i++) for(int j=0;j5505;j+

每天更新java,php,javaScript,go,python,nodejs,vue,android,mysql等相关技术教程,教程由网友分享而来,欢迎大家分享IT技术教程到本站,帮助自己同时也帮助他人!

Copyright 2021, All Rights Reserved. Powered by 跳墙网(www.tqwba.com)|网站地图|关键词