线段树练习四 Description 在平面内有一条长度为n的线段（不计入答案），可以对进行以下2种操作： 1、把从x到y的再加一条线段 2、查询从x到x+1有多少条线段 Input 第一行输入n，m 第2~m+1行，每行2个数x，y，表示从x到y再加一条线段 最后一行输入2个数，为x和x+1，查询x到x+1的线段数目 Output 输出x到x+1的线段数目 Sample Input 7 2 2 5 3 6 4 5 Sample Output 2 Hint 【数据规模】 100%满足1≤n≤100000,1≤x≤y≤n 解题思路 线段树或暴力 线段树练习题一 AC代码（线段树） #includ...

线段树练习五 Description 一行N个方格，开始每个格子里的数都是0。现在动态地提出一些问题和修改：提问的形式是求某一个特定的子区间[a,b]中所有元素的和；修改的规则是指定某一个格子x，加上或者减去一个特定的值A。现在要求你能对每个提问作出正确的回答。1≤N≤100000,提问和修改的总数可能达到100000条。 Input 20 //方格个数 6 //有几组操作 M 1 1 //表示修改,第一个表示格子位置,第二个数表示在原来的基础上加上的数, M 2 2 M 3 4 M 3 -5 M 6 7 C 2 6 //表示统计 ,第一个数表示起始位置,第二个数表示结束位置 Output 8...

滑动窗口 /【模板】单调队列 题目传送门 解题思路 这题就是一道模板题目，我们可以直接用单调队列的单调递增和单调递减来做 单调队列 AC代码 #include<iostream> #include<cstdio> using namespace std; long long n,k,o1,o2,head1,head2,tail1,tail2,a[1000005],b1[1000005],b2[1000005],q1[1000005],q2[1000005],p1[1000005],p2[1000005]; int main() {  scanf("%lld%l...

烽火传递 Description 烽火台又称烽燧，是重要的军事防御设施，一般建在险要或交通要道上。一旦有敌情发生，白天燃烧柴草，通过浓烟表达信息；夜晚燃烧干柴，以火光传递军情，在某两座城市之间有 n 个烽火台，每个烽火台发出信号都有一定代价。为了使情报准确地传递，在连续 m 个烽火台中至少要有一个发出信号。请计算总共最少花费多少代价，才能使敌军来袭之时，情报能在这两座城市之间准确传递。 Input 第一行：两个整数 N，M。其中N表示烽火台的个数， M 表示在连续 m 个烽火台中至少要有一个发出信号。接下来 N 行，每行一个数 Wi，表示第i个烽火台发出信号所需代价。 Output 一行，表示...

假期 Case Time Limit:1000MS Description 经过几个月辛勤的工作，FJ决定让奶牛放假。假期可以在1…N天内任意选择一段（需要连续），每一天都有一个享受指数W。但是奶牛的要求非常苛刻，假期不能短于P天，否则奶牛不能得到足够的休息；假期也不能超过Q天，否则奶牛会玩的腻烦。FJ想知道奶牛们能获得的最大享受指数。 Input 第一行：N,P,Q. 第二行：N个数字，中间用一个空格隔开,每个数都在longint范围内。 Output 一个整数，奶牛们能获得的最大享受指数。 Sample Input 5 2 4 -9 -4 -3 8 -6 Sample Output 5 H...

多重背包 Problem Description 急！灾区的食物依然短缺！ 为了挽救灾区同胞的生命，心系灾区同胞的你准备自己采购一些粮食支援灾区，现在假设你一共有资金n元，而市场有m种大米，每种大米都是袋装产品，其价格不等，并且只能整袋购买。 请问：你用有限的资金最多能采购多少公斤粮食呢？ Input 输入数据首先包含一个正整数C，表示有C组测试用例，每组测试用例的第一行是两个整数n和m(1<=n<=100, 1<=m<=100),分别表示经费的金额和大米的种类，然后是m行数据，每行包含3个数p，h和c(1<=p<=20,1<=h<=200,1&...

琪露诺 题目传送门 解题思路 这题和烽火传递（单调队列）差不多 只不过这个是单调递减（第一位是最大值） 烽火传递是单调递增（第一位是最小值） AC代码 #include<iostream> using namespace std; long long n,l,r,s,head,tail,a[200005],p[200005],f[200005]; int main() {  cin>>n>>l>>r; for(int i=0;i<=n;i++)//从0开始 cin>>a[i],f[i]=-2147483647; head=1;/...

数数  解题思路 这题和假期（单调队列）差不多 AC代码 #include<iostream> using namespace std; long long a,n,k,s,head,tail,p[100005],sum[100005]; int main() {  cin>>n>>k; for(int i=1;i<=n;i++) {  cin>>a; sum[i]=sum[i-1]+a;//前缀和 } s=-2147483647;//初值 head=tail=1; for(int i=1;i<=n;i++) {  while(sum...

Subsequence Problem Description There is a sequence of integers. Your task is to find the longest subsequence that satisfies the following condition: the difference between the maximum element and the minimum element of the subsequence is no smaller than m and no larger than k. 有一个整数序列。 您的任务是查找满足以下条...

股票交易 题目传送门 解题思路 通过一位巨佬的洛谷博客解出来的 用dp+单调队列优化 AC代码 #include<cstdio> #include<iostream> #include<cstring> #include<algorithm> using namespace std; int T,Maxp,w,ap,bp,as,bs,head,tail,p[2005],f[2005][2005]; int main() {  cin>>T>>Maxp>>w; memset(f,128,sizeof(f)); f...

排队 Description n个人排成一条直线（一排），给出队伍中每个人的身高，每个人只能看到站在他右边且个头比他小没有被其他人挡住（跟他身高相同也会挡出他）的人。请求出所有人可以看到的人数之和。 1<=N<=80,000 Sample Input 6 5 10 3 7 4 12 2 Sample Output 5 解题思路 这题就是单挑栈 所谓单调栈，也就是和单调队列差不多，也有单调递增和单调递减 单调递增栈：从栈顶到栈底的元素是严格递增 单调递减栈：从栈顶到栈底的元素是严格递减 但是单调栈只能从栈顶进出，不能从栈底进出 单调栈 AC代码 #include<iostrea...

Largest Rectangle in a Histogram 直方图中最大的矩形 Language: Largest Rectangle in a Histogram Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 36046 Accepted: 11781 Description A histogram is a polygon composed of a sequence of rectangles aligned at a common base line. The rectangles have equal wi...

CF817D Imbalanced Array 题目传送门 解题思路 根据一位巨佬的题解 枚举当前点在什么区间内是最小值和最大值 可以用四个单调栈 一个找当前点为区间最小值时，区间的最左端（minl） 一个找当前点为区间最小值时，区间的最右端（minr） 一个找当前点为区间最大值时，区间的最左端（maxl） 一个找当前点为区间最大值时，区间的最右端（maxr） 最后用一个乘法 a[i]*1ll*(1ll*(i-maxl[i])*(maxr[i]-i)-1ll*(i-minl[i])*(minr[i]-i));  再累加就AC了 注意：要特判 AC代码 #include<cstdio&gt...

Feel Good Description Bill is developing a new mathematical theory for human emotions. His recent investigations are dedicated to studying how good or bad days influent people’s memories about some period of life. A new idea Bill has recently developed assigns a non-negative integer value to each da...