Submission #700995

#	Time	Username	Problem	Language	Result	Execution time	Memory
700995		myrcella	Fire (JOI20_ho_t5)	C++17	100 / 100	266 ms	48544 KiB

ho_t5

//by szh
#include<bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define pii pair<int,int>
#define pll pair<long long,long long>
#define pb push_back
#define debug(x) cerr<<#x<<"="<<x<<endl
#define pq priority_queue
#define inf 0x3f
#define rep(i,a,b) for (int i=a;i<(b);i++)
#define MP make_pair
#define SZ(x) (int(x.size()))
#define ll long long
#define mod 1000000007
#define ALL(x) x.begin(),x.end()
void inc(int &a,int b) {a=(a+b)%mod;}
void dec(int &a,int b) {a=(a-b+mod)%mod;}
int lowbit(int x) {return x&(-x);}
ll p0w(ll base,ll p) {ll ret=1;while(p>0){if (p%2ll==1ll) ret=ret*base%mod;base=base*base%mod;p/=2ll;}return ret;}

const int maxn = 4e5+10;

struct rurq{
	ll tree1[maxn],tree2[maxn];
	void update(ll l,ll r,ll val) {
		int pos = r+1;
		while (pos<maxn) {
			tree1[pos]-=val;
			tree2[pos]-=r*val;
			pos+=lowbit(pos);
		}
		pos = l;
		while (pos<maxn) {
			tree1[pos]+=val;
			tree2[pos]+=(l-1)*val;
			pos+=lowbit(pos);
		}
	}
	ll query(int pos) {
		ll ret = 0;
		int tmp = pos;
		while (pos>0)	 {
			ret += tree1[pos]*tmp;
			ret -= tree2[pos];
			pos-=lowbit(pos);
		}
		return ret;
	}
	ll query(int l,int r) {
		return query(r)-query(l-1);
	}
}vert,diag;

int n,m;
int a[maxn];
int lt[maxn],rt[maxn];
ll ans[maxn];
vector <pair<pii,int>> q[maxn];
vector <pair<pii,int>> upd[maxn];

void tri(int l,int r,int val) {
	if (l>r) return;
	diag.update(l+n+1,n+n+1,val);
	vert.update(r+1+n+1,n+n+1,-val);
	if (r-l+1<=n) upd[r-l+1].pb({{l,r},val});
}

int main() {
//	freopen("input.txt","r",stdin);	
	std::ios::sync_with_stdio(false);cin.tie(0);
	cin>>n>>m;
	rep(i,0,n) cin>>a[i];
	rep(i,0,m) {
		int t,l,r;
		cin>>t>>l>>r;
		l--,r--;
		q[t].pb({{l,r},i});
	}
	stack<int> s;
	rep(i,0,n) {
		while (!s.empty() and a[s.top()]<=a[i]) s.pop();
		if (s.empty()) lt[i] = i-n-1;
		else lt[i] = s.top();
		s.push(i);
	}
	while (!s.empty()) s.pop();
	for (int i =n-1;i>=0;i--) {
		while (!s.empty() and a[s.top()]<a[i]) s.pop();
		if(s.empty()) rt[i] = n;
		else rt[i] = s.top();
		s.push(i);
	}
	rep(i,0,n) {
		tri(lt[i]+1,rt[i]-1,a[i]);
		tri(lt[i]+1,i-1,-a[i]);
		tri(i+1,rt[i]-1,-a[i]);
	}
	debug(vert.query(n+1,2*n) + diag.query(n+1,2*n));
	rep(i,1,n+1) {
		for (auto j:upd[i]) {
			int l = j.fi.fi,r = j.fi.se, val = j.se;
			diag.update(l+n+1,n+n+1,-val);
			vert.update(r+1+n+1,n+n+1,val);
		}
		for (auto j:q[i]) {
			ans[j.se] = vert.query(j.fi.fi+n+1,j.fi.se+n+1) + diag.query(j.fi.fi-i+n+1,j.fi.se-i+n+1);
		}
	}
	rep(i,0,m) cout<<ans[i]<<"\n";
	return 0;
}

• Subtask 1: 1 / 1
• Subtask 2: 6 / 6
• Subtask 3: 7 / 7
• Subtask 4: 6 / 6
• Subtask 5: 80 / 80