首页 > 其他分享 >POJ-3264

POJ-3264

时间:2024-09-05 19:15:40浏览次数:8  
标签:20 dp2 dp1 int POJ 3264

这是rmq
半懂不懂(因为已经会线段树了)
但是!它的代码真的好短啊啊啊啊啊!

#include <bits/stdc++.h>
using namespace std;
int dp1[500010][20],dp2[500010][20],w[1000010];
int main(){
	int n,k,q,l,r;
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>n>>q;
	for(int i=1;i<=n;i++)cin>>w[i],dp1[i][0]=w[i],dp2[i][0]=w[i];
	for(int j=1;1<<j<=n;j++)for(int i=1;i+1<<j-1<=n;i++)dp1[i][j]=min(dp1[i][j-1],dp1[i+(1<<j)-1][j-1]),dp2[i][j]=max(dp2[i][j-1],dp2[i+(1<<j)-1][j-1]);
	for(int i=1;i<=q;i++)cin>>l>>r,k=log2(r-l+1),cout<<max(dp2[l][k],dp2[r-(1<<k)+1][k])-min(dp1[l][k],dp1[r-(1<<k)+1][k])<<endl;
	
}

标签:20,dp2,dp1,int,POJ,3264
From: https://www.cnblogs.com/zan-mei-tai-yang/p/18399074

相关文章

  • POJ - 3150
    题解题意:题面很臭很长。大意是,有一个大小为N的环,给出M,K,D,以及N个数。我们进行K次操作,每次操作把距离当前点不超过D的累加到当前点,结果模M。思路:因为要进行K次,每次的原则是一样的,我们可以想到用矩阵来优化,如果i能到达j,把么base[i][j]=1;则结果ans=A(base^K)。但是需要优化,时间复杂......
  • POJ - 3150
    题解题意:题面很臭很长。大意是,有一个大小为N的环,给出M,K,D,以及N个数。我们进行K次操作,每次操作把距离当前点不超过D的累加到当前点,结果模M。思路:因为要进行K次,每次的原则是一样的,我们可以想到用矩阵来优化,如果i能到达j,把么base[i][j]=1;则结果ans=A(base^K)。但是需要优化,时间复杂......
  • POJ - 3296
    对于操作来说,第一次是最重要的,后来每次倒入水量是相同的。这是因为后面的总液体量不变的情况下,ans=第一次后液体浓度*后几次液体浓度的积所以由1/v^2<1/v^2-x^2(v,x>0),易得后几次水量相同那么,对于第一次来说可以用三分法来求极值。代码:#include<bits/stdc++.h>usingn......
  • POJ-1066
    题解告诉我:大意:在一个矩形区域内,有n条线段,线段的端点是在矩形边上的,有一个特殊点,问从这个点到矩形边的最少经过的线段条数最少的书目,穿越只能在中点穿越思路:需要巧妙的转换一下这个问题,因为从一个点到终点不可能“绕过”围墙,只能穿过去,所以门是否开在中点是无所谓的,只要求四周线......
  • POJ - 3318
    他说:O(n^3)是过不了滴一搜……6代码和题解没有实质区别:#include<cstdio>#include<ctime>#include<cstdlib>usingnamespacestd;inta[505][505],b[505][505],c[505][505];intmain(){ srand(time(NULL)); intn; ios::sync_with_stdio(0); cin.tie(0); while(cin......
  • POJ - 1765
    第一次做扫描线挺好的#include<cstdio>#include<cstring>#include<algorithm>usingnamespacestd;structppx{ intl,r; doubleleft,right; doublelen; intcover;//记录重边情况}tree[4*200+10];doubley[200+10];//对应的序号装对应的边structpp{ doublex......
  • POJ - 1870
    先把蜂巢快递柜画出来:__________/\__/\__/\__/\____/\__/\__/53\__/\__/\__/\__/\__/52\__/54\__/\__/\\__/\__/51\__/31\__/55\__/\__//\__/50\__/30\__/32\__/56\__/\\__/49\__/29\__......
  • POJ - 3318
    他说:O(n^3)是过不了滴一搜……6代码和题解没有实质区别:#include<cstdio>#include<ctime>#include<cstdlib>usingnamespacestd;inta[505][505],b[505][505],c[505][505];intmain(){ srand(time(NULL)); intn; ios::sync_with_stdio(0); cin.tie(0); while(cin......
  • POJ - 2976
    原来是二分谁对平均分贡献大选谁界限<0.001,100次足矣#include<iostream>#include<cstdio>#include<algorithm>#include<cstring>usingnamespacestd;constintmaxn=1010;intn,k;doublemid;structNode{ doublea,b;}w[maxn];boolcmp(Nodex,Nodey......
  • POJ - 3071
    概率题。本蒟蒻不会概率dp,于是手搓枚举。反正爆枚够用后记:SadBee的想法考虑维护每队对上上一队/下一队的胜率。只有两队最简单,用1乘即可那多队呢?不如看成两队。见:P(1胜)=P(1战胜2)P(3战胜4)P(1战胜3)+P(1战胜2)P(4战胜3)P(1战胜4)P(2胜)=......