加强旅游网站建设,微信怎样引流被加精准粉,主机类型wordpress,宜春市住房和城乡建设局网站传送门 文章目录题意#xff1a;思路#xff1a;Update题意#xff1a; 思路#xff1a;
比较神奇的一个题#xff0c;这里先介绍莫队的离线解法。 不难发现#xff0c;用莫队来做最大的难点就是在进行区间移动的时候如何快速计算贡献。 比如[l,r]−[l,r1][l,r]-思路Update题意 思路
比较神奇的一个题这里先介绍莫队的离线解法。 不难发现用莫队来做最大的难点就是在进行区间移动的时候如何快速计算贡献。 比如[l,r]−[l,r1][l,r]-[l,r1][l,r]−[l,r1]的时候多出来的区间就是[l,r1],[l1,r1],...,[r1,r1][l,r1],[l1,r1],...,[r1,r1][l,r1],[l1,r1],...,[r1,r1]如何快速计算其贡献呢 我们考虑维护一个数组f[i]f[i]f[i]表示以iii为结尾的每个后缀的答案要保证这些后缀都是不交的区间即后缀的若干区间应该是类似于这种形式[x,i],[y,x−1],...,[1,h−1][x,i],[y,x-1],...,[1,h-1][x,i],[y,x−1],...,[1,h−1]为了转移方便考虑记pre[i]pre[i]pre[i]表示左边第一个≤a[i]\le a[i]≤a[i]的位置这个用单调栈可以很快维护出来转移方程f[i](i−pre[i])∗a[i]f[pre[i]]f[i](i-pre[i])*a[i]f[pre[i]]f[i](i−pre[i])∗a[i]f[pre[i]] 考虑这个怎么用显然我们不能直接加上f[r1]f[r1]f[r1]因为f[r1]f[r1]f[r1]包含了[1,x],[x1,y],...,[z1,r1][1,x],[x1,y],...,[z1,r1][1,x],[x1,y],...,[z1,r1]这若干段区间的贡献而我们要算的贡献是[l,r1][l,r1][l,r1]之间的贡献显然这两个区间是有可能不交的当然也不能写成f[r1]−f[l−1]f[r1]-f[l-1]f[r1]−f[l−1]的形式除非f[r1]f[r1]f[r1]包含的区间中几段拼起来正好有[l,r1][l,r1][l,r1]这样才可以。那么我们往这个思路上靠是否能找到个位置pospospos使得[pos1,r1][pos1,r1][pos1,r1]的区间能通过f[r1]−f[pos]f[r1]-f[pos]f[r1]−f[pos]直接得到贡献并且[l,pos][l,pos][l,pos]区间的贡献也能快速计算呢考虑求fff数组的过程我们是找左边≤a[i]\le a[i]≤a[i]的最近的位置那么我们要是能找到[l,r1][l,r1][l,r1]中的最小值的位置就可以计算了显然这个可以STSTST表预处理出来之后再预处理一下另一边的即可那么这个题就结束啦代码还是比较好调的。 实在有点不明白为什么这个题莫队的指针移动顺序对答案有影响按照莫队的原理来说顺序是随意的可能这个先加后减是有什么影响真是为数不多指针移动顺序的有影响的题了。。。等弄懂了再写原因吧。 复杂度O(nlognnn)O(nlognn\sqrt n)O(nlognnn)
Update
在线做法 继续考虑我们的fff数组我们还是找一个最小的位置pospospos让后分成两个区间[l,pos),(pos,r][l,pos),(pos,r][l,pos),(pos,r]当左端点在左边区间右端点在右边区间的时候贡献就是(pos−l1)∗(r−pos1)∗a[pos](pos-l1)*(r-pos1)*a[pos](pos−l1)∗(r−pos1)∗a[pos]现在就剩左右端点分别在左边和右边区间了这里只考虑做右端点都在右边的在左边同理。 考虑如果右端点在rrr左端点在(pos,r](pos,r](pos,r]的时候的答案为f[r]−f[pos]f[r]-f[pos]f[r]−f[pos]右端点在r−1r-1r−1左端点在(pos,r−1](pos,r-1](pos,r−1]的时候答案为f[r−1]−f[pos]f[r-1]-f[pos]f[r−1]−f[pos]…我们定义sumi∑j1ifjsum_i\sum_{j1}^if_jsumi∑j1ifj那么在(pos,r](pos,r](pos,r]的贡献就是gr−gpos−(r−pos)∗fposg_r-g_{pos}-(r-pos)*f_{pos}gr−gpos−(r−pos)∗fpos右边区间同理。 复杂度O(nlogn)O(nlogn)O(nlogn)
O(nlognnn)O(nlognn\sqrt n)O(nlognnn)
// Problem: P3246 [HNOI2016]序列
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P3246
// Memory Limit: 500 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)//#pragma GCC optimize(Ofast,no-stack-protector,unroll-loops,fast-math)
//#pragma GCC target(sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tunenative)
//#pragma GCC optimize(2)
#includecstdio
#includeiostream
#includestring
#includecstring
#includemap
#includecmath
#includecctype
#includevector
#includeset
#includequeue
#includealgorithm
#includesstream
#includectime
#includecstdlib
#includerandom
#includecassert
#define X first
#define Y second
#define L (u1)
#define R (u1|1)
#define pb push_back
#define mk make_pair
#define Mid ((tr[u].ltr[u].r)1)
#define Len(u) (tr[u].r-tr[u].l1)
#define random(a,b) ((a)rand()%((b)-(a)1))
#define db puts(---)
using namespace std;//void rd_cre() { freopen(d://dp//data.txt,w,stdout); srand(time(NULL)); }
//void rd_ac() { freopen(d://dp//data.txt,r,stdin); freopen(d://dp//AC.txt,w,stdout); }
//void rd_wa() { freopen(d://dp//data.txt,r,stdin); freopen(d://dp//WA.txt,w,stdout); }typedef long long LL;
typedef unsigned long long ULL;
typedef pairint,int PII;const int N1000010,mod1e97,INF0x3f3f3f3f;
const double eps1e-6;int n,m;
int a[N],block;
int stk[N],top,suf[N],pre[N];
LL psum[N],ssum[N];
struct Node {int l,r,id;
}q[N];bool cmp(Node a,Node b)
{int la(a.l-1)/block1,lb(b.l-1)/block1;return la^lb? lalb : ((la1)? a.rb.r:a.rb.r);
}int f[N][30];
double len[N];
void init()
{for(int i1;in;i) f[i][0]i;int tlog2(n)1;for(int j1;jt;j)for(int i1;in-(1j)1;i) {if(a[f[i][j-1]]a[f[i(1ll(j-1))][j-1]]) f[i][j]f[i][j-1];else if(a[f[i][j-1]]a[f[i(1ll(j-1))][j-1]]) f[i][j]f[i(1ll(j-1))][j-1];else if(a[f[i][j-1]]a[f[i(1ll(j-1))][j-1]]) f[i][j]max(f[i][j-1],f[i(1ll(j-1))][j-1]);}
}int query(int l,int r) {int tlen[r-l1];if(a[f[l][t]]a[f[r-(1t)1][t]]) return f[l][t];else if(a[f[l][t]]a[f[r-(1t)1][t]]) return f[r-(1t)1][t];return max(f[l][t],f[r-(1t)1][t]);
}LL ans[N],sum;void addl(int l,int r) {int posquery(l,r);sum1ll*(r-pos1)*a[pos]ssum[l]-ssum[pos];
}void addr(int l,int r) {int posquery(l,r);sum1ll*(pos-l1)*a[pos]psum[r]-psum[pos];
}void dell(int l,int r) {int posquery(l,r);sum-1ll*(r-pos1)*a[pos]ssum[l]-ssum[pos];
}void delr(int l,int r) {int posquery(l,r);sum-1ll*(pos-l1)*a[pos]psum[r]-psum[pos];
}int main()
{
// ios::sync_with_stdio(false);
// cin.tie(0);cinnm; blocksqrt(n);for(int i1;in;i) len[i]log2(i);for(int i1;in;i) scanf(%d,a[i]); init();for(int i1;im;i) scanf(%d%d,q[i].l,q[i].r),q[i].idi;sort(q1,q1m,cmp);for(int i1;in;i) {while(topa[stk[top]]a[i]) suf[stk[top--]]i;pre[i]stk[top]; stk[top]i;}while(top) pre[stk[top]]stk[top-1],suf[stk[top--]]n1;for(int i1;in;i) psum[i]1ll*(i-pre[i])*a[i]psum[pre[i]];for(int in;i1;i--) ssum[i]1ll*(suf[i]-i)*a[i]ssum[suf[i]];int l1,r0;for(int i1;im;i) {int lxq[i].l,rxq[i].r;while(llx) addl(--l,r);while(rrx) addr(l,r);while(rrx) delr(l,r--);while(llx) dell(l,r);ans[q[i].id]sum;}for(int i1;im;i) printf(%lld\n,ans[i]);return 0;
}
O(nlogn)O(nlogn)O(nlogn)
// Problem: P3246 [HNOI2016]序列
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P3246
// Memory Limit: 500 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)//#pragma GCC optimize(Ofast,no-stack-protector,unroll-loops,fast-math)
//#pragma GCC target(sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tunenative)
//#pragma GCC optimize(2)
#includecstdio
#includeiostream
#includestring
#includecstring
#includemap
#includecmath
#includecctype
#includevector
#includeset
#includequeue
#includealgorithm
#includesstream
#includectime
#includecstdlib
#includerandom
#includecassert
#define X first
#define Y second
#define L (u1)
#define R (u1|1)
#define pb push_back
#define mk make_pair
#define Mid ((tr[u].ltr[u].r)1)
#define Len(u) (tr[u].r-tr[u].l1)
#define random(a,b) ((a)rand()%((b)-(a)1))
#define db puts(---)
using namespace std;//void rd_cre() { freopen(d://dp//data.txt,w,stdout); srand(time(NULL)); }
//void rd_ac() { freopen(d://dp//data.txt,r,stdin); freopen(d://dp//AC.txt,w,stdout); }
//void rd_wa() { freopen(d://dp//data.txt,r,stdin); freopen(d://dp//WA.txt,w,stdout); }typedef long long LL;
typedef unsigned long long ULL;
typedef pairint,int PII;const int N1000010,mod1e97,INF0x3f3f3f3f;
const double eps1e-6;int n,m;
int a[N],block;
int stk[N],top;
LL suf[N],pre[N];
LL psum[N],ssum[N];int f[N][30];
double len[N];
void init()
{for(int i1;in;i) f[i][0]i;int tlog2(n)1;for(int j1;jt;j)for(int i1;in-(1j)1;i) {if(a[f[i][j-1]]a[f[i(1ll(j-1))][j-1]]) f[i][j]f[i][j-1];else if(a[f[i][j-1]]a[f[i(1ll(j-1))][j-1]]) f[i][j]f[i(1ll(j-1))][j-1];else if(a[f[i][j-1]]a[f[i(1ll(j-1))][j-1]]) f[i][j]max(f[i][j-1],f[i(1ll(j-1))][j-1]);}
}int query(int l,int r) {int tlen[r-l1];if(a[f[l][t]]a[f[r-(1t)1][t]]) return f[l][t];else if(a[f[l][t]]a[f[r-(1t)1][t]]) return f[r-(1t)1][t];return max(f[l][t],f[r-(1t)1][t]);
}int main()
{
// ios::sync_with_stdio(false);
// cin.tie(0);cinnm; for(int i1;in;i) len[i]log2(i);for(int i1;in;i) scanf(%d,a[i]); init();for(int i1;in;i) {while(topa[stk[top]]a[i]) suf[stk[top--]]i;pre[i]stk[top]; stk[top]i;}while(top) pre[stk[top]]stk[top-1],suf[stk[top--]]n1;for(int i1;in;i) psum[i]1ll*(i-pre[i])*a[i]psum[pre[i]];for(int in;i1;i--) ssum[i]1ll*(suf[i]-i)*a[i]ssum[suf[i]];for(int i1;in;i) pre[i]pre[i-1]psum[i];for(int in;i1;i--) suf[i]suf[i1]ssum[i];while(m--) {int l,r; scanf(%d%d,l,r);int posquery(l,r);LL ans1ll*(pos-l1)*(r-pos1)*a[pos];anspre[r]-pre[pos]-psum[pos]*(r-pos);anssuf[l]-suf[pos]-ssum[pos]*(pos-l);printf(%lld\n,ans);}return 0;
}
