相关链接
题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4826
神犇题解:http://www.cnblogs.com/Enceladus/p/6735887.html
解题报告
这题建出笛卡尔树,之后就是区间加、区间询问
于是将询问离线,用线段树维护一下就好了
总时间复杂度:$O(n \log n)$
至于笛卡尔树那一块,我们可以看作一个分治
而与最大值相关的题,分治是常见解法
所以这题还是很容易想到的吧
Code
#include<bits/stdc++.h> #define LL long long using namespace std; const int N = 200009; const int NN = N << 1; const int M = 18; int n,m,p1,p2,val[N]; LL ans[N]; vector<int> q1[N]; vector<pair<int,int> > q2[N],q3[N]; struct Query{int l,r,id;}q[N]; inline bool cmp1(const Query &A, const Query &B) {return A.r < B.r;} inline bool cmp2(const Query &A, const Query &B) {return A.l > B.l;} inline int read() { char c=getchar(); int f=1,ret=0; while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();} while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();} return ret * f; } class Sparse_Table{ int mx[M][N],pos[M][N],lg[N]; public: inline void init(int *arr) { for (int i=1;i<=n;i++) { mx[0][i] = arr[i]; pos[0][i] = i; } for (int l=1,j=1;l*2<=n;j++,l<<=1) { for (int i=1;i<=n-l;i++) { if (mx[j-1][i] >= mx[j-1][i+l]) { pos[j][i] = pos[j-1][i]; mx[j][i] = mx[j-1][i]; } else { pos[j][i] = pos[j-1][i+l]; mx[j][i] = mx[j-1][i+l]; } } } for (int i=2;i<=n;i++) { lg[i] = lg[i>>1] + 1; } } inline int query(int l, int r) { int t = lg[r-l+1], j = 1 << t; if (mx[t][l] >= mx[t][r-j+1]) return pos[t][l]; else return pos[t][r-j+1]; } }ST; void solve(int l, int r) { if (l == r - 1) { return; } else { int pos = ST.query(l+1, r-1); if (l) q1[pos].push_back(l); if (r <= n) q1[r].push_back(pos); if (r <= n && pos - l > 1) q2[r].push_back(make_pair(l + 1, pos - 1)); if (l && r - pos > 1) q3[l].push_back(make_pair(pos + 1, r - 1)); solve(l, pos); solve(pos, r); } } class Segment_Tree{ int cnt; LL AnsTmp; struct Node{ Node *ch[2]; int len; LL sum,tag; }p[NN],*root; public: inline void init() { cnt = 0; build(root, 1, n); } inline void modify(int pos, int delta) { Node *w = root; int l = 1, r = n, mid; while (l <= r) { w->sum += delta; if (l == r) break; mid = l + r + 1 >> 1; if (pos < mid) w = w->ch[0], r = mid - 1; else w = w->ch[1], l = mid; } } inline void modify(int l, int r, int delta) { modify(root, 1, n, l, r, delta); } inline LL query(int l, int r) { AnsTmp = 0; query(root, 1, n, l, r); return AnsTmp; } private: inline void pushdown(Node *w) { w->ch[0]->sum += w->ch[0]->len * w->tag; w->ch[1]->sum += w->ch[1]->len * w->tag; w->ch[0]->tag += w->tag; w->ch[1]->tag += w->tag; w->tag = 0; } void query(Node *w, int l, int r, int L, int R) { if (L <= l && r <= R) { AnsTmp += w->sum; } else { if (w->tag) pushdown(w); int mid = l + r + 1 >> 1; if (L < mid) query(w->ch[0], l, mid-1, L, R); if (mid <= R) query(w->ch[1], mid, r, L, R); } } void modify(Node *w, int l, int r, int L, int R, int delta) { if (L <= l && r <= R) { w->sum += (LL)delta * w->len; w->tag += delta; } else { if (w->tag) pushdown(w); int mid = r + l + 1 >> 1; if (L < mid) modify(w->ch[0], l, mid-1, L, R, delta); if (mid <= R) modify(w->ch[1], mid, r, L, R, delta); w->sum = w->ch[0]->sum + w->ch[1]->sum; } } void build(Node *&w, int l, int r) { w = &p[++cnt]; w->len = r - l + 1; w->sum = w->tag = 0; w->ch[0] = w->ch[1] = 0; if (l < r) { int mid = l + r + 1 >> 1; build(w->ch[0], l, mid-1); build(w->ch[1], mid, r); } } }SEG; int main() { n = read(); m = read(); p1 = read(); p2 = read(); for (int i=1;i<=n;i++) { val[i] = read(); } ST.init(val); solve(0, n+1); for (int i=1;i<=m;i++) { q[i].l = read(); q[i].r = read(); q[i].id = i; } sort(q+1, q+1+m, cmp1); SEG.init(); for (int i=1,pos=0;i<=m;i++) { while (pos < q[i].r) { pos++; for (int j=0;j<q1[pos].size();j++) { SEG.modify(q1[pos][j], p1); } for (int j=0;j<q2[pos].size();j++) { SEG.modify(q2[pos][j].first, q2[pos][j].second, p2); } } ans[q[i].id] += SEG.query(q[i].l, q[i].r); } sort(q+1, q+1+m, cmp2); SEG.init(); for (int i=1,pos=n+1;i<=m;i++) { while (pos > q[i].l) { pos--; for (int j=0;j<q3[pos].size();j++) { SEG.modify(q3[pos][j].first, q3[pos][j].second, p2); } } ans[q[i].id] += SEG.query(q[i].l, q[i].r); } for (int i=1;i<=m;i++) { printf("%lld\n",ans[i]); } return 0; }