This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
typedef pair<int,int> pi;
typedef vector <int> vi;
typedef vector <pi> vpi;
typedef pair<pi, ll> pii;
typedef set <ll> si;
typedef long double ld;
#define f first
#define s second
#define mp make_pair
#define FOR(i,s,e) for(int i=s;i<=int(e);++i)
#define DEC(i,s,e) for(int i=s;i>=int(e);--i)
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define lbd(x, y) lower_bound(all(x), y)
#define ubd(x, y) upper_bound(all(x), y)
#define aFOR(i,x) for (auto i: x)
#define mem(x,i) memset(x,i,sizeof x)
#define fast ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define maxn 400010
#define INF (ll)1e9
#define MOD 1000000007
typedef pair <vi, int> pvi;
typedef pair <int,pi> ipi;
typedef vector <pii> vpii;
#define DEBUG 0
int S[maxn];
int N,Q;
int t,l,r;
vpi queries[maxn];
int ans[maxn];
struct FW{
int fw[maxn],N;
FW(int _N){
N = _N;
FOR(i,1,N) fw[i] = 0;
}
void upd(int p,int v){
assert(p != 0);
for (int i=p;i<=N;i+=i&(-i)) fw[i] += v;
}
int pref_qry(int p){
int ans = 0;
for (int i=p;i>0;i-=i&(-i)) ans += fw[i];
return ans;
}
int suff_qry(int p){
return pref_qry(N) - pref_qry(p-1);
}
void print(){
FOR(i,1,N) cout << pref_qry(i) - pref_qry(i-1) << ' ';
cout << '\n';
}
};
int A[maxn],B[maxn],C[maxn],W[maxn];
int32_t main(){
fast;
// Let an edge a->b be such that a is the greatest index < b such that S[a] >= S[b]
// Edges are indexed by b
// Let c be the maximum value of a node in b's subtree
// Let w be S[a] - S[b]
cin >> N >> Q;
FOR(i,1,N) cin >> S[i];
FW normalfw = FW(N);
FOR(i,1,N) normalfw.upd(i,S[i]);
FOR(i,1,Q){
cin >> t >> l >> r;
ans[i] += normalfw.pref_qry(r) - normalfw.pref_qry(l-1);
queries[r].pb({t,i});
queries[l-1].pb({t,-i});
}
FW fixfw_wcb = FW(2*N), fixfw_wab = FW(2*N), fixfw_w = FW(2*N), fixfw_wab2 = FW(2*N), fixfw_w2 = FW(2*N);
FW stackfw_w = FW(2*N), stackfw_wb = FW(2*N), stackfw_wab = FW(2*N), stackfw_wab2 = FW(2*N), stackfw_w2 = FW(2*N);
// Fixed fenwicks indexed on c-a
// Stack fenwicks indexed on a
//
// fixfw_wcb stores sum of w(c-b)
// fixfw_wab stores sum of w(a-b)
// fixfw_w stores sum of w
// stackfw_w stores sum of w
// stackfw_wb stores sum of wb
// stackfw_wab stores sum of w(a-b)
stack <int> st;
int shift = 0;
FOR(i,1,N){
while (!st.empty() && S[st.top()] < S[i]){
int x = st.top();
if (A[x] != -1){
stackfw_w.upd(A[x], -W[x]);
stackfw_wb.upd(A[x], -W[x]*x);
stackfw_wab.upd(A[x], -W[x]*(A[x]-x));
stackfw_w2.upd(x-A[x], -W[x]);
stackfw_wab2.upd(x-A[x], -W[x]*(A[x]-x));
C[x] += shift; // transfer updates from stack
fixfw_wcb.upd(C[x] - A[x], W[x]*(C[x]-x));
fixfw_wab.upd(C[x] - A[x], W[x]*(A[x]-x));
fixfw_w.upd(C[x] - A[x], W[x]);
fixfw_w2.upd(x - A[x], W[x]);
fixfw_wab2.upd(x - A[x], W[x]*(A[x]-x));
}
st.pop();
}
shift++; // increase all C by 1 in the stack
if (!st.empty()){
A[i] = st.top();
C[i] = i - shift; // have to take into account stack updates
W[i] = S[A[i]] - S[i];
stackfw_w.upd(A[i], W[i]);
stackfw_wb.upd(A[i], W[i]*i);
stackfw_wab.upd(A[i], W[i]*(A[i]-i));
stackfw_w2.upd(i-A[i], W[i]);
stackfw_wab2.upd(i-A[i], W[i]*(A[i]-i));
}else A[i] = -1;
st.push(i);
if (DEBUG && i == N){
cout << "FIX\n";
cout << "wcb "; fixfw_wcb.print();
cout << "w "; fixfw_w.print();
cout << "wab "; fixfw_wab.print();
cout << "w2 "; fixfw_w2.print();
cout << "wab2 "; fixfw_wab2.print();
cout << "STACK\n";
cout << "w "; stackfw_w.print();
cout << "wb "; stackfw_wb.print();
cout << "wab "; stackfw_wab.print();
cout << "w2 "; stackfw_w2.print();
cout << "wab2 "; stackfw_wab2.print();
}
aFOR(q, queries[i]){
int t = q.f;
int fix = fixfw_wcb.pref_qry(t) + fixfw_w.suff_qry(t+1)*t + fixfw_wab.suff_qry(t+1) - fixfw_w2.suff_qry(t+1)*t - fixfw_wab2.suff_qry(t+1) + fixfw_w2.pref_qry(t);
int sta = stackfw_w.suff_qry(i-t) * i - stackfw_wb.suff_qry(i-t) + stackfw_w.pref_qry(i-t-1)*t + stackfw_wab.pref_qry(i-t-1) - stackfw_w2.suff_qry(t+1)*t - stackfw_wab2.suff_qry(t+1) + stackfw_w2.pref_qry(t);
assert(fix >= 0 && sta >= 0);
if (q.s < 0) ans[abs(q.s)] -= fix + sta;
else ans[abs(q.s)] += fix + sta;
}
}
while (!st.empty()){
C[st.top()] += shift; st.pop();
}
if (DEBUG) FOR(i,1,N) cout << A[i] << ' ' << C[i] << ' ' << W[i] << '\n';
FOR(i,1,Q) cout << ans[i] << '\n';
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |