相关链接
题目传送门: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;
}