Submission #878538

#	Time	Username	Problem	Language	Result	Execution time	Memory
878538		winter0101	Fire (JOI20_ho_t5)	C++14	100 / 100	421 ms	77500 KiB

ho_t5

#include<bits/stdc++.h>
using namespace std;
#define all(fl) fl.begin(),fl.end()
#define pb push_back
#define fi first
#define se second
#define for1(i,j,k) for(int i=j;i<=k;i++)
#define for2(i,j,k) for(int i=j;i>=k;i--)
#define for3(i,j,k,l) for(int i=j;i<=k;i+=l)
#define lb lower_bound
#define ub upper_bound
#define sz(a) (int)a.size()
#define pii pair<int,int>
#define pli pair<long long,int>
#define gcd __gcd
#define lcm(x,y) x*y/__gcd(x,y)
#define lastbit(i) __builtin_ctz(i)
const int maxn=2e5+9;
int a[maxn];
vector<pii>b[maxn];
struct BIT{
vector<long long>bit;
int n;
void resz(int _n){
n=_n;
bit.resize(n+1);
}
void add(int pos,long long val){
for(;pos<=n;pos+=(pos-(pos&(pos-1))))bit[pos]+=val;
}
long long get(int pos){
long long ans=0;
for(;pos>=1;pos-=(pos-(pos&(pos-1))))ans+=bit[pos];
return ans;
}
long long get(int l,int r){
if (l>r)return 0;
return get(r)-get(l-1);
}
};
int in[maxn],out[maxn],tme=0,st[maxn][19];
vector<pii>add[maxn],del[maxn],add2[maxn],del2[maxn];
long long ans[maxn];
BIT cnt,bit;
BIT t1,t2,t3,t4;
int n,q;
int par[maxn];
void predfs(int u){
in[u]=++tme;
for (auto v:add[u]){
int tmp=u;
for2(j,18,0){
if (!st[tmp][j]||!par[st[tmp][j]])continue;
int pr=par[st[tmp][j]];
if (v.fi+pr>=u){
tmp=st[tmp][j];
}
}
if (st[tmp][0]&&par[st[tmp][0]]&&v.fi+par[st[tmp][0]]<u){
tmp=st[tmp][0];
add2[tmp].pb(v);
//cout<<tmp<<'\n';
}
}
for (auto v:del[u]){
int tmp=u;
for2(j,18,0){
if (!st[tmp][j]||!par[st[tmp][j]])continue;
int pr=par[st[tmp][j]];
if (v.fi+pr>=u){
tmp=st[tmp][j];
}
}
if (st[tmp][0]&&par[st[tmp][0]]&&v.fi+par[st[tmp][0]]<u){
tmp=st[tmp][0];
del2[tmp].pb(v);
}
}
for (auto v:b[u]){
st[v.fi][0]=u;
for1(i,1,18)st[v.fi][i]=st[st[v.fi][i-1]][i-1];
predfs(v.fi);
}
out[u]=tme;
}
void solve(int u){
if (par[u]){
int diff=par[u];
long long w=a[par[u]]-a[u];
t1.add(diff,-w*(u-1));
t2.add(diff,w);
diff=u-par[u];
t3.add(diff,-1ll*w*(diff-1));
t4.add(diff,w);
}
for (auto v:add2[u]){
ans[v.se]+=1ll*v.fi*t4.get(v.fi)+t3.get(v.fi);
}
for (auto v:del2[u]){
ans[v.se]-=1ll*v.fi*t4.get(v.fi)+t3.get(v.fi);
}
for (auto v:add[u]){
//cout<<bit.get(v.fi)<<'\n';
ans[v.se]+=1ll*v.fi*cnt.get(v.fi)+bit.get(v.fi);
//cout<<max(u-v.fi,1)<<'\n';
//cout<<t2.get(n)<<'\n';
ans[v.se]+=1ll*u*t2.get(max(u-v.fi,1),n)+t1.get(max(u-v.fi,1),n);
}
for (auto v:del[u]){
ans[v.se]-=1ll*v.fi*cnt.get(v.fi)+bit.get(v.fi);
ans[v.se]-=1ll*u*t2.get(max(u-v.fi,1),n)+t1.get(max(u-v.fi,1),n);
}
for (auto v:b[u]){
solve(v.fi);
}
if (par[u]){
    int diff=par[u];
    long long w=a[par[u]]-a[u];
    t1.add(diff,w*(u-1));
    t2.add(diff,-w);
    diff=u-par[u];
    t3.add(diff,1ll*w*(diff-1));
    t4.add(diff,-w);
}
if (par[u]){
int sz=out[u]-in[u]+1;
int time=u-par[u];
bit.add(time+sz,1ll*(a[par[u]]-a[u])*sz);
long long value=(a[par[u]]-a[u]);
value*=(time-1);
//update poly
bit.add(time,-value);
bit.add(time+sz,value);
cnt.add(time,(a[par[u]]-a[u]));
cnt.add(time+sz,-(a[par[u]]-a[u]));
}
}
long long pf[maxn];
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    //freopen("temp.INP","r",stdin);
    //freopen("temp.OUT","w",stdout);
    cin>>n>>q;
    cnt.resz(n);
    t3.resz(n);
    t4.resz(n);
    bit.resz(n);
    t1.resz(n);
    t2.resz(n);
    for1(i,1,n)cin>>a[i];
    for1(i,1,n)pf[i]=pf[i-1]+a[i];
    a[0]=1e9+7;
    stack<int>t;
    t.push(0);
    vector<int>root;
    for1(i,1,n){
    while (!t.empty()&&a[t.top()]<=a[i])t.pop();
    int p=t.top();
    if (p)b[p].pb({i,i-p});
    else root.pb(i);
    par[i]=t.top();
    t.push(i);
    }
    for1(i,1,q){
    int t,l,r;
    cin>>t>>l>>r;
    add[r].pb({t,i});
    del[l-1].pb({t,i});
    ans[i]+=pf[r]-pf[l-1];
    }
    for (auto v:root)predfs(v);
    for (auto v:root)solve(v);
    for1(i,1,q)cout<<ans[i]<<'\n';
}

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