夏休み合宿----データ構造

84706 ワード

FSYの良い問題のまとめ

CF 377 D Developing Gameは、m a x(l i)≦m i i n(v i)max(l_i)\le min(v)max(li)max(l i)≦min(vi)、m a x(v i)≦m i i n(r i)max(vui)\min(rcul)\min(ruL)min(llllmi i i i i i i i i i i i i i))))(rvix(llllllllllllllllllllllllllllllllllllllllllllllllllllllllmmi i)))))i)］R∈[m a x(v i)m i n(r i)]L\n[max(luui)、m in(vui)]、R\in[max(vui)、min(rcui)]L∈[max(li)]、min[max(vi)、min(ri)発見(L,l,R)に対応しています.i,v_i,r_i li、vi、riはマトリクスに対応しています.スキャンラインはCF 646 E The Class ic Problemを見てください.一番短絡するにはどの操作をサポートしますか?pを1にしたら主席ツリーで実現できます.

#include
#define N 200000
using namespace std;
int read(){
	int cnt = 0, f = 1; char ch = 0;
	while(!isdigit(ch)){ ch = getchar(); if(ch == '-') f = -1;}
	while(isdigit(ch)) cnt = (cnt << 1) + (cnt << 3) + (ch-'0'), ch = getchar();
	return cnt * f;
}
int n, m, first[N], nxt[N<<1], to[N<<1], w[N<<1], tot;
void add(int x, int y, int z){
	nxt[++tot] = first[x], first[x] = tot, to[tot] = y, w[tot] = z;
}
typedef long long ll;
const int Base = 2, Mod = 1e9 + 7;
const int up = 150000;
ll Mul[N]; int st, ed, rt[N], idx;
struct President{
	int ls, rs; ll sum;
}t[N * 100];
int modify(int last, int &x, int l, int r, int pos){
	x = ++idx; t[x] = t[last];
	if(l == r){ t[x].sum = t[last].sum ^ 1; return t[last].sum;}
	int mid = (l+r) >> 1, res = 0;
	if(pos <= mid){
		res = modify(t[last].ls, t[x].ls, l, mid, pos);
		if(res) res = modify(t[last].rs, t[x].rs, mid+1, r, pos);
	}
	else res = modify(t[last].rs, t[x].rs, mid+1, r, pos);
	t[x].sum = (t[t[x].rs].sum * Mul[mid-l+1] % Mod + t[t[x].ls].sum) % Mod; return res;
}
bool Comp(int a, int b, int l, int r){
	if(l == r) return t[a].sum > t[b].sum;
	int mid = (l+r) >> 1;
	if(t[t[a].rs].sum == t[t[b].rs].sum) return Comp(t[a].ls, t[b].ls, l, mid);
	else return Comp(t[a].rs, t[b].rs, mid+1, r);
} 
int from[N]; bool vis[N];
struct Node{
	int x, rt;
	Node(int _x = 0, int _rt = 0){ x = _x; rt = _rt;}
	bool operator < (const Node &a) const{ return Comp(rt, a.rt, 0, up);}
}; priority_queue q;
void Print(int x, int dep){
	if(x == st){ printf("%d
%d ", dep, x); return;}
	Print(from[x], dep+1); printf("%d ", x);
}
void Dijsktra(){
	q.push(Node(st, rt[st]));
	while(!q.empty()){
		int x = q.top().x, rot = q.top().rt; q.pop();
		if(vis[x]) continue; vis[x] = true;
		if(rt[x] != rot) continue;
		if(x == ed){ printf("%lld
", t[rt[ed]].sum); Print(x, 1); return;}
		for(int i = first[x]; i; i = nxt[i]){
			int t = to[i]; int now = 0; modify(rt[x], now, 0, up, w[i]);
			if(!rt[t] || Comp(rt[t], now, 0, up)){
				from[t] = x;
				rt[t] = now; q.push(Node(t, rt[t])); 
			}
		}
	} puts("-1");
}
int main(){
	n = read(), m = read();
	Mul[0] = 1;
	for(int i = 1; i <= up; i++) Mul[i] = Mul[i-1] * Base % Mod;
	for(int i = 1; i <= m; i++){
		int x = read(), y = read(), z = read();
		add(x, y, z); add(y, x, z);
	} st = read(), ed = read();
	Dijsktra(); return 0;
}

CF 755 F Meta-universeの暴力的なやり方はx x x xまたはy y yによって並べられ、x,y x,y,yをスキャンして両方に切りますが、これが一番悪いのはO(n 2)O(n^2)O(n 2)の任然として暴力的なやり方です.小さい集合の大きさを考慮して、大きな集合を一つの小さな集合と一つの大きな集合に分けることができます.いくつかの発見式のような統合用の小さい集合の大きさが大きな集合に結合できるので、複雑さはO(n l o g n 2)O(nlogn^2)O(nlogn 2)と呼ばれます.

#include
using namespace std;
int read(){
	int cnt = 0, f = 1; char ch = 0;
	while(!isdigit(ch)){ ch = getchar(); if(ch == '-') f = -1;}
	while(isdigit(ch)) cnt = (cnt << 1) + (cnt << 3) + (ch-'0'), ch = getchar();
	return cnt * f;
}
struct Point{ int x, y; };
struct cmp1{ bool operator () (const Point &a, const Point &b){ return a.x < b.x || (a.x == b.x && a.y < b.y); }};
struct cmp2{ bool operator () (const Point &a, const Point &b){ return a.y < b.y || (a.y == b.y && a.x < b.x); }};
typedef set Sx;
typedef set Sy;
typedef Sx::iterator Itx;
typedef Sy::iterator Ity;
Sx sx; Sy sy;
int n, ans;
void Split(Sx &S1, Sy &S2){
	Itx lx = S1.begin(), rx = --S1.end();
	Ity ly = S2.begin(), ry = --S2.end();
	int n = S1.size() >> 1;
	for(int i = 1; i <= n; i++){
		Itx tp = lx++;
		if(tp->x + 1 < lx->x){
			Sx S3; Sy S4; lx = ++tp;
			for(tp = S1.begin(); tp != lx;){
				Itx now = tp++;
				S3.insert(*now);
				S4.insert(*now);
				S2.erase(*now);
				S1.erase(now);
			} Split(S1, S2); Split(S3, S4);
			return;
		}
		tp = rx--;
		if(rx->x + 1 < tp->x){
			Sx S3; Sy S4; rx = --tp;
			for(tp = --S1.end(); tp != rx;){
				Itx now = tp--;
				S3.insert(*now);
				S4.insert(*now);
				S2.erase(*now);
				S1.erase(now);
			} Split(S1, S2); Split(S3, S4);
			return;
		}
		tp = ly++;
		if(tp->y + 1 < ly->y){
			Sx S3; Sy S4; ly = ++tp;
			for(tp = S2.begin(); tp != ly;){
				Ity now = tp++;
				S3.insert(*now);
				S4.insert(*now);
				S2.erase(now);
				S1.erase(*now);
			} Split(S1, S2); Split(S3, S4);
			return;
		}
		tp = ry--;
		if(ry->y + 1 < tp->y){
			Sx S3; Sy S4; ry = --tp;
			for(tp = --S2.end(); tp != ry;){
				Ity now = tp--;
				S3.insert(*now);
				S4.insert(*now);
				S2.erase(now);
				S1.erase(*now);
			} Split(S1, S2); Split(S3, S4);
			return;
		}
	} ++ans;
}
int main(){
	n = read();
	while(n--){
		int x = read(), y = read(); Point now = (Point){x, y};
		sx.insert(now); sy.insert(now);
	} Split(sx, sy); cout << ans; return 0;
}

CF 643 G Choosing Adsは絶対数のO(n)O(n)O(n)O(n)のやり方を考慮して、一つの桶と現在の数を維持します.もし参加したのが現在数ではないなら、個数–逆の個数＋＋を考慮して、もし個数<0<0>を現在の数に置き換えれば、明らかに出現回数が半分を超える数は減少されないという問題も同じです.一つの区間の数は左半分の5つか、右半分の5つか、線分樹p u s h up pusshup pusup up upの場合は上の考え方で加減すればいいです.

#include
#define N 150050
using namespace std;
int read(){
	int cnt = 0, f = 1; char ch = 0;
	while(!isdigit(ch)){ ch = getchar(); if(ch == '-') f = -1;}
	while(isdigit(ch)) cnt = (cnt << 1) + (cnt << 3) + (ch-'0'), ch = getchar();
	return cnt * f;
}
int n, m, p;
int a[N];
struct tree{
	int num, tag, a[5], b[5];
	tree operator + (const tree &A){
		tree res = A; res.tag = 0;
		for(int i = 0; i < num; i++){
			bool flag = 0;
			for(int j = 0; j < res.num; j++){
				if(a[i] == res.a[j]){ flag = 1; res.b[j] += b[i]; break;}
			}
			if(flag) continue;
			if(res.num < p){ res.a[res.num] = a[i]; res.b[res.num] = b[i]; ++res.num; continue;}
			int k = 0;
			for(int j = 1; j < res.num; j++) if(res.b[j] < res.b[k]) k = j;
			if(b[i] < res.b[k]){ for(int j = 0; j < res.num; j++) res.b[j] -= b[i];}
			else{
				int tmp = res.b[k];
				res.a[k] = a[i]; res.b[k] = b[i];
				for(int j = 0; j < res.num; j++) res.b[j] -= tmp;
			}
		} return res;
	} 
} t[N<<2];
void build(int x, int l, int r){
	if(l == r){ t[x].a[0] = a[l]; t[x].b[0] = t[x].num = 1; return;}
	int mid = (l+r) >> 1; build(x<<1, l, mid); build(x<<1|1, mid+1, r);
	t[x] = t[x<<1] + t[x<<1|1];
}
void pushnow(int x, int l, int r, int v){
	t[x].num = 1; t[x].a[0] = v; t[x].b[0] = r - l + 1; t[x].tag = v;
}
void pushdown(int x, int l, int r){
	if(t[x].tag){ 
		int mid = (l+r) >> 1;
		pushnow(x<<1, l, mid, t[x].tag);
		pushnow(x<<1|1, mid+1, r, t[x].tag);
		t[x].tag = 0;
	}
}
void modify(int x, int l, int r, int L, int R, int v){
	if(L<=l && r<=R){ pushnow(x, l, r, v); return;} 
	pushdown(x, l, r); int mid = (l+r) >> 1;
	if(L<=mid) modify(x<<1, l, mid, L, R, v);
	if(R>mid) modify(x<<1|1, mid+1, r, L, R, v);
	t[x] = t[x<<1] + t[x<<1|1];
}
tree query(int x, int l, int r, int L, int R){
	if(L<=l && r<=R) return t[x]; pushdown(x, l, r); 
	int mid = (l+r) >> 1;
	if(L>mid) return query(x<<1|1, mid+1, r, L, R);
	else if(R<=mid) return query(x<<1, l, mid, L, R);
	else return query(x<<1, l, mid, L, R) + query(x<<1|1, mid+1, r, L, R);
}
int main(){
	n = read(), m = read(), p = read(); p = 100 / p;
	for(int i = 1; i <= n; i++) a[i] = read();
	build(1, 1, n);
	while(m--){
		int op = read(), l = read(), r = read();
		if(op == 1) modify(1, 1, n, l, r, read()); 
		if(op == 2){
			tree ans = query(1, 1, n, l, r); 
			cout << ans.num << " ";
			for(int i = 0; i < ans.num; i++) cout << ans.a[i] << " ";
			puts("");
		}
	} return 0;
}

CF 533 E Little Pony and Lord Tirekは、馬ごとに血がいっぱいになる時間t＿i t＿_を先に算出することができます.i tiその後区間[l,r][l,r]間の馬に対してt＿i t_を押します.i ti並べ替え、二つに分けて前の方に血をいっぱい入れて、後ろの方は全部s u m(m i)、s u m(r i)sum(mui)、sum(ruui)sum(mi)、sum(ri)を処理していません.t i t_を押してください.i tiは下标建主席の木がきれいなだけで、どんな操作をサポートしますか?

#include
#define N 100050
using namespace std;
typedef long long ll;
const int up = 100000;
int n, m, s[N], mx[N], rp[N];
int b[N], c[N]; ll sum[N];
#define pi pair
#define mp make_pair
pi operator + (const pi &a, const pi &b){ return mp(a.first + b.first, a.second + b.second);}
struct Presidentree{
	bool op;
	int rt[N], ls[N * 20], rs[N * 20], node;
	ll val[N * 20], sum[N * 20];
	void modify(int &x, int las, int l, int r, int pos, int p){
		x = ++node; ls[x] = ls[las]; rs[x] = rs[las];
		val[x] = val[las] + rp[p]; sum[x] = sum[las] + mx[p] - (op ? 0 : s[p]);
		if(l == r) return; int mid = (l+r) >> 1;
		if(pos <= mid) modify(ls[x], ls[las], l, mid, pos, p);
		else modify(rs[x], rs[las], mid+1, r, pos, p);
	}
	pi query(int a, int b, int l, int r, int L, int R){
		if(!a) return mp(0, 0);
		if(L<=l && r<=R) return mp(val[a] - val[b], sum[a] - sum[b]);
		int mid = (l + r) >> 1; pi ans = mp(0, 0);
		if(L<=mid) ans = ans + query(ls[a], ls[b], l, mid, L, R);
		if(R>mid) ans = ans + query(rs[a], rs[b], mid+1, r, L, R);
		return ans;
	}
}T[2];
struct Node{ 
	int l, r, v; 
	Node(int _l = 0, int _r = 0, int _v = 0):l(_l),r(_r),v(_v){}
	bool operator < (const Node &a) const{ return l < a.l;}
};
set S;
typedef set::iterator Int;
Int split(int p){
	Int it = S.lower_bound(Node(p));
	if(it != S.end() && it->l == p) return it;
	it--;
	int l = it->l, r = it->r, v = it->v;
	S.erase(it);
	S.insert(Node(l, p - 1, v));
	it = S.lower_bound(Node(l, p - 1, v));
	return S.insert(Node(p, r, v)).first;
}
ll ask(int t, int x, int y){
	Int R = split(y + 1), L = split(x);
	ll ans = sum[y] - sum[x - 1];
	for(Int it = L; it != R; it++){
		pi res;
		if(it->v == 0) res = T[0].query(T[0].rt[it->r], T[0].rt[it->l - 1], 0, up + 1, min(up + 1, t - it->v + 1), up + 1);
		else res = T[1].query(T[1].rt[it->r], T[1].rt[it->l - 1], 0, up + 1, min(up + 1, t - it->v + 1), up + 1);
		ans += 1ll * res.first * (t - it->v) - res.second;
	} S.erase(L, R); S.insert(Node(x, y, t));
	return ans;
}
int main(){
	scanf("%d", &n);
	for(int i = 1; i <= n; i++){
		scanf("%d%d%d", &s[i], &mx[i], &rp[i]);
		sum[i] = sum[i-1] + (ll)mx[i];
		if(rp[i] == 0) b[i] = c[i] = up + 1;
		else{ 
			b[i] = (mx[i] - s[i]) / rp[i] + ((mx[i] - s[i]) % rp[i] > 0);
			c[i] = mx[i] / rp[i] + (mx[i] % rp[i] > 0);
		}
	} T[0].op = 0; T[1].op = 1;
	for(int i = 1; i <= n; i++) T[0].modify(T[0].rt[i], T[0].rt[i-1], 0, up + 1, b[i], i);
	for(int i = 1; i <= n; i++) T[1].modify(T[1].rt[i], T[1].rt[i-1], 0, up + 1, c[i], i);
	S.insert(Node(1, n, 0)); S.insert(Node(n + 1, n + 1, 0));
	scanf("%d", &m);
	while(m--){
		int t, l, r; scanf("%d%d%d", &t, &l, &r);
		cout << ask(t, l, r) << '
';
	} return 0;
}

CF 997 E Good Subsegments 1セグメントが良いと、m a x(a i)−m i(a i)＝r−−−−−−max(a)−m i n(a)＝r−a−i(a)−a−i(a)−a(a)＝r−i(a)−i(a)−i−−−−−−−r−l)についてお問い合わせを線から離します.r−a(r−i)で並べ替えて、r−a(a(a−a−a(a)−a(a−i)−a−a(a(a)−a−a)−a(a(a)−a)−a−a(a)−i)−i)−a(a−a(a(a)−i)−a(a x(a i)−m i n(ai)−(r−l)の最小値と最小値の個数を考慮して、a i a_を追加します.i aiの貢献は、各位置r rに対して+1と同時に単調なスタックを維持し、a i a a_に対してi aiはm a a x maxの区間として、a i−m a x a a_を統合します.i-max ai−max,m i n min同理でr rまで行って、線分樹で［l,r］［l,r］［l,r］の0の個数などを調べます.ここで調べたのは強制的にrを選んだのです.明らかに違います.そして、rを掃いた後にマークを付けて、現在のrが答えに対する貢献を下に置くことを表します.

#include
#define N 200050
using namespace std;
typedef long long ll;
int n, m, a[N], mi[N], mx[N], top1, top2;
int Min[N<<2], sum[N<<2], ti[N<<2], tag[N<<2]; ll ans[N<<2], Ans[N];
struct qu{ int l, r, id;} q[N];
bool cmp(qu a, qu b){ return a.r < b.r;}
void pushmi(int x, int v){ Min[x] += v; tag[x] += v;}
void pushti(int x, int v){ ans[x] += 1ll * sum[x] * v; ti[x] += v;}
void pushdown(int x){
	if(tag[x]){ pushmi(x<<1, tag[x]); pushmi(x<<1|1, tag[x]); tag[x] = 0;}
	if(ti[x]){ 
		if(Min[x<<1] == Min[x]) pushti(x<<1, ti[x]);
		if(Min[x<<1|1] == Min[x]) pushti(x<<1|1, ti[x]);
		ti[x] = 0;
	}
}
void pushup(int x){
	Min[x] = min(Min[x<<1], Min[x<<1|1]); sum[x] = 0;
	if(Min[x] == Min[x<<1]) sum[x] += sum[x<<1];
	if(Min[x] == Min[x<<1|1]) sum[x] += sum[x<<1|1];
	ans[x] = ans[x<<1] + ans[x<<1|1];
} 
void build(int x, int l, int r){
	sum[x] = 1; Min[x] = l;
	if(l == r) return; int mid = (l+r) >> 1; 
	build(x<<1, l, mid); build(x<<1|1, mid+1, r);
}
void modify(int x, int l, int r, int L, int R, int v){
	if(L<=l && r<=R){ pushmi(x, v); return;} 
	pushdown(x); int mid = (l+r) >> 1;
	if(L<=mid) modify(x<<1, l, mid, L, R, v);
	if(R>mid) modify(x<<1|1, mid+1, r, L, R, v);
	pushup(x);
} 
ll query(int x, int l, int r, int L, int R){
	if(L<=l && r<=R) return ans[x]; pushdown(x);
	int mid = (l+r) >> 1; ll ret = 0; 
	if(L<=mid) ret += query(x<<1, l, mid, L, R);
	if(R>mid) ret += query(x<<1|1, mid+1, r, L, R);
	return ret;
}
int main(){
	scanf("%d", &n); 
	for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
	build(1, 1, n);
	scanf("%d", &m);
	for(int i = 1; i <= m; i++) scanf("%d%d", &q[i].l, &q[i].r), q[i].id = i;
	sort(q+1, q+m+1, cmp);
	for(int i = 1, j = 1; i <= n; i++){
		while(top1 && a[i] < a[mi[top1]]){
			modify(1, 1, n, mi[top1-1] + 1, mi[top1], a[mi[top1]] - a[i]);
			top1--;
		} mi[++top1] = i;
		while(top2 && a[i] > a[mx[top2]]){
			modify(1, 1, n, mx[top2-1] + 1, mx[top2], a[i] - a[mx[top2]]);
			top2--;
		} mx[++top2] = i;
		pushmi(1, -1);
		pushti(1, 1);
		while(j <= m && q[j].r == i) Ans[q[j].id] = query(1, 1, n, q[j].l, q[j].r), ++j;
	}
	for(int i = 1; i <= m; i++) cout << Ans[i] << "
";
	return 0;
}

CF 108 3 D The Fair Nut’s getting crazyは、列挙区間[b,c][b,c]、[b,c]を考慮し、l i,r i l_を記録する.i,r_i i i i i i i i i i,iは色iの前の後ろに位置しますが、条件を満たすのはm a x(l i)c max(l_i)c,a𕑑[m a x(l i),b),d_c[mamamamamamamax](((=mamamamamamamamamamamamamai)))))))))))))))))[mamamamamamamamamamamamamamamamamamamamamamamamamamamamamamamamax[87a[i]]]]]]]]]]]](((((b)、d∈[c,m i n(r i)前の問題のように、列挙c、メンテナンスΣb(b−m x)(m i−c)\sumub(b-mx)(m-mx)(m i-c)Σb(b−mx)(mi−mx)(mi−c)Σb(b−m x)(m i−c)=Σb b b b b-m m i i i i i i i i i i i i i m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m+87 x(87 x x+m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m m-m x*m i-b*c+c*mxΣb(b−mx)(mi−c)=Σb b∗m i−m x∗mi−b∗c+c∗mxはそれぞれi i iについて、i i i i*i*mi、m i単調mi、m x mx、m＿x*mi x、m＿i＿x x*mi x、m＿x x*mi xを維持する必要があります.

#include
#define N 200050
using namespace std;
typedef long long ll;
const int Mod = 1e9+7;
int L[N], R[N], a[N], b[N], lst[N];
int mi[N], top1, mx[N], top2, n; ll ans;
void Add(ll &a, ll b){ a = a + b; if(a >= Mod) a -= Mod;}
ll add(ll a, ll b){ return (a + b) % Mod;}
ll mul(ll a, ll b){ return a * b % Mod; }
struct Node{
	ll mx, mi, mxi, pmi, mit, mxt;
	void merge(Node a, Node b){ 
		mx = add(a.mx, b.mx), mi = add(a.mi, b.mi);
		mxi = add(a.mxi, b.mxi); pmi = add(a.pmi, b.pmi);
	}
}t[N<<2];
void pushup(int x){t[x].merge(t[x<<1], t[x<<1|1]);}
ll f(ll x){ return (x * (x + 1) / 2) % Mod;}
void pushmi(int x, int l, int r, int v){
	Add(t[x].mit, v);
	Add(t[x].mi, mul(v, r-l+1));
	Add(t[x].mxi, mul(v, t[x].mx));
	Add(t[x].pmi, mul(v, add(f(r), Mod-f(l-1))));
}
void pushmx(int x, int l, int r, int v){
	Add(t[x].mxt, v);
	Add(t[x].mx, mul(v, r-l+1));
	Add(t[x].mxi, mul(v, t[x].mi));
}
void pushdown(int x, int l, int r){
	int mid = (l+r) >> 1;
	if(t[x].mit){ pushmi(x<<1, l, mid, t[x].mit); pushmi(x<<1|1, mid+1, r, t[x].mit); t[x].mit = 0;}
	if(t[x].mxt){ pushmx(x<<1, l, mid, t[x].mxt); pushmx(x<<1|1, mid+1, r, t[x].mxt); t[x].mxt = 0;} 
}
void modify(int x, int l, int r, int L, int R, int v, int op){
	if(L<=l && r<=R){ 
		if(!op) pushmi(x, l, r, v);
		else pushmx(x, l, r, v);
		return;
	} pushdown(x, l, r); int mid = (l+r) >> 1;
	if(L<=mid) modify(x<<1, l, mid, L, R, v, op);
	if(R>mid) modify(x<<1|1, mid+1, r, L, R, v, op);
	pushup(x);
}
Node query(int x, int l, int r, int L, int R){
	if(L<=l && r<=R) return t[x]; pushdown(x, l, r);
	int mid = (l+r) >> 1; Node ans = (Node){0, 0, 0, 0, 0, 0};
	if(L<=mid) ans.merge(ans, query(x<<1, l, mid, L, R));
	if(R>mid) ans.merge(ans, query(x<<1|1, mid+1, r, L, R));
	return ans;
}
int main(){
	scanf("%d", &n);
	for(int i = 1; i <= n; i++) scanf("%d", &a[i]), b[i] = a[i];
	sort(b + 1, b + n + 1); int siz = unique(b+1, b+n+1) - (b+1);
	for(int i = 1; i <= n; i++) a[i] = lower_bound(b+1, b+siz+1, a[i]) - b;
	for(int i = 1; i <= n; i++){
		L[i] = lst[a[i]] + 1; lst[a[i]] = i;
	}
	for(int i = 1; i <= siz; i++) lst[i] = n + 1;
	for(int i = n; i >= 1; i--){
		R[i] = lst[a[i]] - 1; lst[a[i]] = i;
	}
	for(int i = 1, pos = 1; i <= n; i++){
		while(top1 && L[i] >= L[mx[top1]]){
			modify(1, 1, n, mx[top1-1]+1, mx[top1], Mod-L[mx[top1]], 1);
			top1--;
		} modify(1, 1, n, mx[top1] + 1, i, L[i], 1); mx[++top1] = i;
		while(top2 && R[i] <= R[mi[top2]]){
			modify(1, 1, n, mi[top2-1]+1, mi[top2], Mod-R[mi[top2]], 0);
			top2--;
		} modify(1, 1, n, mi[top2] + 1, i, R[i], 0); mi[++top2] = i;
		pos = max(pos, L[i]);
		Node res = query(1, 1, n, pos, i);
		ll tmp = Mod - mul(i, add(f(i), Mod - f(pos-1)));
		Add(tmp, Mod - res.mxi);
		Add(tmp, res.pmi);
		Add(tmp, mul(i, res.mx));
		Add(ans, tmp);
	} cout << ans; return 0;
}

高精度乗算高精度除法