一个网站如何挣钱,wordpress仿站视频,惠州市两学一做网站,深圳尚石设计有限公司LOJBZOJ 参考这儿qwq。 首先询问都是求#xff0c;向左走的最短路。\(f[i][j]\)表示从\(i\)走到\(j\)最少需要多少步。表示这样只会\(O(n^2\log n)\)的 但是感觉能卡过\(70\)分。 注意到从\(i\)出发#xff0c;走\(j\)步能到达的点都是一段一段的。所以不妨令\(f[i][j]\)表示… LOJBZOJ 参考这儿qwq。 首先询问都是求向左走的最短路。\(f[i][j]\)表示从\(i\)走到\(j\)最少需要多少步。表示这样只会\(O(n^2\log n)\)的 但是感觉能卡过\(70\)分。 注意到从\(i\)出发走\(j\)步能到达的点都是一段一段的。所以不妨令\(f[i][j]\)表示从\(i\)出发走\(j\)步能到达的最左边的是什么。那么\(f[i][j1]\min\limits_{kf[i][j]}^{i-1}L[k]\)。 但是我们还没有考虑向右走的情况。可以发现一条路径最多只会向右走一次。 那么判一下就好惹。这样就可以\(O(n^2)\)啦。 注意到这一过程实际可以倍增\(f[i][j]\)表示从\(i\)出发走\(2^j\)步最左可以到哪。但是还要考虑第一步向右走的情况所以不妨直接令它表示\(i\sim n\)这些点走\(2^j\)步最左可以到哪。 记\(Calc(i,p)\)表示从\(i\)分别走到\(p\sim i\)所有点总共需要走多远。把询问\([l,r]\)拆成\(Calc(i,l)-Calc(i,r1)\)。 那么再维护一个\(sum[i][j]\)表示从\(i\)出发分别走到\(f[i][j]\sim i\)总共需要走多远。那么\(sum[i][j]sum[i][j-1]sum[f[i][j-1]][j-1](f[i][j]-f[i][j-1])\times2^{j-1}\)。 具体\(Calc\)的时候关于向右走一步的处理不妨直接让\(i\)先向左走一步走到\(L[i]\)。这样\(L[i]\)左边的部分都有可能需要\(i\)向右走但是这正好符合\(f\)的定义同时我们已经跳了一步也可以看作向右跳了一步。 注意维护一个变量\(tot\)表示之前一共跳过了多少距离。 还有主席树的做法我不写惹qwq 懒。 //3272ms 68628K / 69284kb 8496ms
#include cstdio
#include cctype
#include algorithm
#define BIT 18
#define gc() getchar()
#define MAXIN 500000
//#define gc() (SSTT(TT(SSIN)fread(IN,1,MAXIN,stdin),SSTT)?EOF:*SS)
typedef long long LL;
const int N3e55;int L[N],f[BIT1][N];
LL sum[BIT1][N];
char IN[MAXIN],*SSIN,*TTIN;inline int read()
{int now0;register char cgc();for(;!isdigit(c);cgc());for(;isdigit(c);nownow*10c-48,cgc());return now;
}
int Gcd(int a,int b)
{return b?Gcd(b,a%b):a;
}
LL Calc(int l,int p,const int bit)
{if(L[p]l) return p-l;LL ansp-L[p],tot1; pL[p];for(int ibit; ~i; --i)if(f[i][p]l) anssum[i][p](p-f[i][p])*tot, tot1i, pf[i][p];return ans(p-l)*(tot1);//(r-l)*totr-l
}int main()
{const int nread(); int bit23;while(1bitn) --bit;for(int i2; in; i) L[i]read();f[0][n]L[n];for(int in-1; i; --i) f[0][i]std::min(f[0][i1],L[i]), sum[0][i]i-f[0][i];for(int j1; jbit; j){LL t1llj-1;for(int i1; in; i)f[j][i]f[j-1][f[j-1][i]], sum[j][i]sum[j-1][i]sum[j-1][f[j-1][i]](f[j-1][i]-f[j][i])*t;}for(int Qread(); Q--; ){int lread(),rread(),xread(),br-l1;LL aCalc(l,x,bit)-Calc(r1,x,bit); int gGcd(b,a%b);printf(%lld/%d\n,a/g,b/g);}return 0;
} 转载于:https://www.cnblogs.com/SovietPower/p/10734771.html
