bzoj 4540 序列

Posted on | Views:

线段树.

  • 这道题显然有一个莫队的做法,但它是带根号的,不够优秀.考虑用一个 $O(nlogn)$ 的做法解决它.
  • 考虑将询问离线下来,从 $1$ 到 $n$ 依次加入元素,当前已经加入了第 $p$ 个元素,对每个位置维护 $val_i,sum_i$ ,分别表示区间 $[i,p]$ 的最小值,以及 $val_i$ 所有历史版本值之和.若 $i>p$ ,则当前 $val_i=0$ .
  • 加入第 $p$ 个元素后,立即回答所有 $r=p$ 的询问,答案显然是 $\sum_{i=l}^r sum_i$ .
  • 于是我们只需要用一颗线段树来维护 $val,sum$ 这两个值(的区间和)即可.
  • 考虑加入第 $p$ 个元素后如何修改 $val,sum$ .可以通过单调栈求出最小的 $i$ ,使得 $[i,p]$ 内最小值都为 $a_p$ .需要将 $[i,p]$ 这个区间内的 $val$ 都修改成 $a_p$ ,并让区间 $[1,p]$ 内的 $sum$ 加上对应位置新的 $val$.

  • 时间复杂度 $O(nlogn)$ .
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read()
{
	int out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		fh=-1,jp=getchar();
	while (jp>='0'&&jp<='9')
		out=out*10+jp-'0',jp=getchar();
	return out*fh;
}
const int MAXN=1e5+10;
int n,Q,A[MAXN];
ll ans[MAXN];
struct Query
{
	int l,id;
	Query(int l=0,int id=0):l(l),id(id) {}
};
vector<Query> V[MAXN];
int stk[MAXN],tp=0;
struct tag
{
	ll a,b,c,d;
	void init(){a=1;b=c=d=0;}
	tag(int a,int b,int c,int d):a(a),b(b),c(c),d(d) {}
	tag(){init();}
	bool valid()
	{
		if(a==1 && !b && !c && !d)
			return false;
		return true;
	}
	tag operator + (const tag &rhs) const
	{
		tag Newtag;
		Newtag.a=rhs.a*a;
		Newtag.b=rhs.a*b+rhs.b;
		Newtag.c=rhs.c*a+c;
		Newtag.d=rhs.c*b+d+rhs.d;
		return Newtag;
	}
};
struct SegTree
{
	struct node
	{
		ll val,sum,len;
		tag t;
		bool TagValid()
		{
			return t.valid();
		}
	} Tree[MAXN<<2];
#define root Tree[o]
#define lson Tree[o<<1]
#define rson Tree[o<<1|1]
	void BuildTree(int o,int l,int r)
	{
		root.val=root.sum=0;
		root.len=r-l+1;
		if(l==r)
			return;
		int mid=(l+r)>>1;
		BuildTree(o<<1,l,mid);
		BuildTree(o<<1|1,mid+1,r);
	}
	void pushup(int o)
	{
		root.val=lson.val+rson.val;
		root.sum=lson.sum+rson.sum;
	}
	void Modifiy(int o,tag Newtag)
	{
		root.sum+=Newtag.c*root.val+Newtag.d*root.len;
		root.val=Newtag.a*root.val+Newtag.b*root.len;
		root.t=root.t+Newtag;
	}
	void pushdown(int o)
	{
		if(root.TagValid())
		{
			Modifiy(o<<1,root.t);
			Modifiy(o<<1|1,root.t);
			(root.t).init();
		}
	}
	void upd(int o,int l,int r,int L,int R,tag Newtag)
	{
		if(L<=l && r<=R)
		{
			Modifiy(o,Newtag);
			return;
		}
		pushdown(o);
		int mid=(l+r)>>1;
		if(L<=mid)
			upd(o<<1,l,mid,L,R,Newtag);
		if(R>mid)
			upd(o<<1|1,mid+1,r,L,R,Newtag);
		pushup(o);
	}
	ll query(int o,int l,int r,int L,int R)
	{
		if(L<=l && r<=R)
			return root.sum;
		pushdown(o);
		int mid=(l+r)>>1;
		ll res=0;
		if(L<=mid)
			res+=query(o<<1,l,mid,L,R);
		if(R>mid)
			res+=query(o<<1|1,mid+1,r,L,R);
		return res;
	}
}T;
int main()
{
	n=read(),Q=read();
	for(int i=1; i<=n; ++i)
		A[i]=read();
	for(int i=1; i<=Q; ++i)
	{
		int l=read(),r=read();
		V[r].push_back(Query(l,i));
	}
	T.BuildTree(1,1,n);
	for(int p=1; p<=n; ++p)
	{
		while(tp && A[p]<A[stk[tp]])
			--tp;
		int i=stk[tp]+1;
		stk[++tp]=p;
		tag Newtag=tag(0,A[p],0,0);
		T.upd(1,1,n,i,p,Newtag);
		Newtag=tag(1,0,1,0);
		T.upd(1,1,n,1,p,Newtag);
		int siz=V[p].size();
		for(int j=0; j<siz; ++j)
			ans[V[p][j].id]=T.query(1,1,n,V[p][j].l,p);	
	}
	for(int i=1; i<=Q; ++i)
		printf("%lld\n",ans[i]);
	return 0;
}