#include <bits/stdc++.h>
using namespace std;
#define a first
#define b second
#define pb push_back
typedef long long llo;
#define endl '\n'
llo n,q;
llo it[200001];
llo pre6[200001];
llo par[200001];
llo vis[200001];
llo fin[200001];
vector<llo> adj[200001];
vector<pair<pair<llo,llo>,llo>> pre[200001];
llo ind[200001];
//llo pre[200001];
vector<llo> pre3[200001];
vector<pair<llo,llo>> tt;
llo ss[200001];
vector<llo> pre4[200001];
void dfs(llo no){
vis[no]=1;
ss[no]=1;
for(auto j:adj[no]){
par[j]=no;
dfs(j);
ss[no]+=ss[j];
llo te=j-no;
tt.pb({j-te,j});
pre3[j-no].pb(j);
pre4[(j-no)+ss[j]].pb(j);
//time j-no duration ss[no]
}
}
llo tree[4*20001][2];
void update(llo no,llo l,llo r,llo i,llo aa,llo bb){
/* if(no==0){
cout<<i<<",,"<<aa<<",,"<<bb<<endl;
}*/
if(l==r){
tree[no][0]=aa;
tree[no][1]=-bb*aa;
}
else{
llo mid=(l+r)/2;
if(i<=mid){
update(no*2+1,l,mid,i,aa,bb);
}
else{
update(no*2+2,mid+1,r,i,aa,bb);
}
tree[no][0]=tree[no*2+1][0]+tree[no*2+2][0];
tree[no][1]=tree[no*2+1][1]+tree[no*2+2][1];
}
}
pair<llo,llo> query2(llo no,llo l,llo r,llo aa,llo bb){
if(r<aa or l>bb or aa>bb){
return {0,0};
}
if(aa<=l and r<=bb){
return {tree[no][0],tree[no][1]};
}
llo mid=(l+r)/2;
pair<llo,llo> x=query2(no*2+1,l,mid,aa,bb);
pair<llo,llo> y=query2(no*2+2,mid+1,r,aa,bb);
return {x.a+y.a,x.b+y.b};
}
vector<pair<llo,llo>> tree2[4*200001];
vector<llo> tree3[4*200001][2];
vector<llo> ind2[4*200001];
void build(llo no,llo l,llo r){
for(llo j=l;j<=r;j++){
tree2[no].pb({tt[j].b,j-l});
}
sort(tree2[no].begin(),tree2[no].end());
for(llo j=1;j<=r-l+2;j++){
tree3[no][0].pb(0);
tree3[no][1].pb(0);
ind2[no].pb(-1);
}
for(llo j=0;j<tree2[no].size();j++){
ind2[no][tree2[no][j].b]=j;
}
if(l<r){
llo mid=(l+r)/2;
build(no*2+1,l,mid);
build(no*2+2,mid+1,r);
}
}
void uu(llo no,llo i,pair<llo,llo> x){
while(i<tree3[no][0].size()){
tree3[no][0][i]+=x.a;
tree3[no][1][i]+=x.b;
i+=(i&-i);
}
}
pair<llo,llo> s2(llo no,llo i){
llo su=0;
llo su2=0;
while(i>0){
su+=tree3[no][0][i];
su2+=tree3[no][1][i];
i-=(i&-i);
}
return {su,su2};
}
void update3(llo no,llo l,llo r,llo i,pair<llo,llo> x){
llo xa=ind2[no][i-l];
//cout<<xa<<"::"<<endl;
/*if(i==3){
cout<<x.a<<"???????????????"<<xa<<endl;
}*/
uu(no,xa+1,x);
if(l<r){
llo mid=(l+r)/2;
if(i<=mid){
update3(no*2+1,l,mid,i,x);
}
else{
update3(no*2+2,mid+1,r,i,x);
}
}
}
pair<llo,llo> query3(llo no,llo l,llo r,llo aa,llo bb,llo i){
if(r<aa or l>bb or aa>bb){
return {0,0};
}
if(aa<=l and r<=bb){
llo low=-1;
/* if(3>=l and 3<=r){
cout<<l<<"<"<<r<<endl;
for(auto jj:tree2[no]){
cout<<jj.a<<";;"<<jj.b<<endl;
}
}*/
for(llo j=19;j>=0;j--){
if(low+(1<<j)<tree2[no].size()){
if(tree2[no][low+(1<<j)].a<=i){
low+=(1<<j);
}
}
}
/* if(3>=l and 3<=r){
cout<<low<<"//"<<s2(no,low+1).a<<endl;
}*/
return s2(no,low+1);
}
else{
llo mid=(l+r)/2;
pair<llo,llo> xx=query3(no*2+1,l,mid,aa,bb,i);
pair<llo,llo> yy=query3(no*2+2,mid+1,r,aa,bb,i);
return {xx.a+yy.a,xx.b+yy.b};
}
}
llo tree4[4*200001];
llo lazy[4*200001];
void push(llo no,llo l,llo r){
tree4[no]+=lazy[no]*(r-l+1);
if(l<r){
lazy[no*2+1]+=lazy[no];
lazy[no*2+2]+=lazy[no];
}
lazy[no]=0;
}
void update2(llo no,llo l,llo r,llo aa,llo bb,llo x){
push(no,l,r);
if(r<aa or l>bb){
return;
}
if(aa<=l and r<=bb){
lazy[no]=x;
push(no,l,r);
}
else{
llo mid=(l+r)/2;
update2(no*2+1,l,mid,aa,bb,x);
update2(no*2+2,mid+1,r,aa,bb,x);
tree4[no]=tree4[no*2+1]+tree4[no*2+2];
}
}
llo query(llo no,llo l,llo r,llo aa,llo bb){
push(no,l,r);
if(r<aa or l>bb or aa>bb){
return 0;
}
if(aa<=l and r<=bb){
return tree4[no];
}
llo mid=(l+r)/2;
llo x=query(no*2+1,l,mid,aa,bb);
llo y=query(no*2+2,mid+1,r,aa,bb);
tree4[no]=tree4[no*2+1]+tree4[no*2+2];
return x+y;
}
int solve(llo i,llo j){
llo low=-1;
for(llo ii=19;ii>=0;ii--){
if(low+(1<<ii)<tt.size()){
if(tt[low+(1<<ii)].a<=j-i){
low+=(1<<ii);
}
}
}
llo su=0;
if(low>=0){
pair<llo,llo> xx=query2(0,0,n-1,0,low);
// cout<<xx.a<<"????"<<endl;
su+=xx.b;
su+=xx.a*(i+1);
// cout<<su<<",,,"<<endl;
}
//cout<<low<<"??"<<endl;
if(low+1<tt.size()){
pair<llo,llo> yy=query3(0,0,tt.size()-1,low+1,tt.size()-1,j);
su+=yy.b;
su+=(j+1)*yy.a;
// cout<<yy.a<<",,"<<yy.b<<endl;
}
return su;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin>>n>>q;
vector<pair<llo,llo>> ss5;
for(llo i=0;i<n;i++){
cin>>it[i];
pre6[i+1]=pre6[i]+it[i];
while(ss5.size()){
if(ss5.back().a<it[i]){
ss5.pop_back();
}
else{
break;
}
}
if(ss5.size()){
adj[ss5.back().b].pb(i);
}
ss5.pb({it[i],i});
}
for(llo i=0;i<n;i++){
if(vis[i]==0){
dfs(i);
}
}
sort(tt.begin(),tt.end());
for(llo i=0;i<tt.size();i++){
ind[tt[i].b]=i;
}
for(llo ii=0;ii<q;ii++){
llo t,l,r;
cin>>t>>l>>r;
l--;
r--;
pre[t].pb({{l,r},ii});
if(tt.size()==0){
cout<<pre6[r+1]-pre6[l]<<endl;
}
}
if(tt.size()==0){
return 0;
}
build(0,0,tt.size()-1);
/* for(auto j:tt){
cout<<j.a<<":"<<j.b<<endl;
}
cout<<endl;*/
for(llo i=1;i<=n;i++){
//cout<<i<<":"<<endl;
for(auto j:pre3[i]){
//cout<<j<<",,"<<ind[j]<<endl;
llo x=it[par[j]]-it[j];
//cout<<j<<"+"<<endl;
update(0,0,n-1,ind[j],x,i);
//cout<<11<<endl;
update3(0,0,tt.size()-1,ind[j],{x,-j*x});
}
//continue;
for(auto j:pre4[i]){
// cout<<j<<"-"<<endl;
//cout<<j<<"?"<<j+ss[j]-1<<"?"<<it[par[j]]-it[j]<<endl;
update2(0,0,n-1,j,j+ss[j]-1,it[par[j]]-it[j]);
update(0,0,n-1,ind[j],0,0);
llo x=it[par[j]]-it[j];
update3(0,0,tt.size()-1,ind[j],{-x,j*x});
}
for(auto jj:pre[i]){
pair<llo,llo> j=jj.a;
llo cur=pre6[j.b+1]-pre6[j.a];
//cout<<cur<<"::"<<endl;
cur+=query(0,0,n-1,j.a,j.b);
//continue;
//cout<<cur<<",,"<<endl;///<<tree4[0]<<endl;
cur+=solve(i,j.b);
if(j.a>0){
cur-=solve(i,j.a-1);
}
fin[jj.b]=cur;
}
}
for(int i=0;i<q;i++){
cout<<fin[i]<<endl;
}
return 0;
}
Compilation message
ho_t5.cpp: In function 'void build(llo, llo, llo)':
ho_t5.cpp:84:15: warning: comparison of integer expressions of different signedness: 'llo' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
84 | for(llo j=0;j<tree2[no].size();j++){
| ~^~~~~~~~~~~~~~~~~
ho_t5.cpp: In function 'void uu(llo, llo, std::pair<long long int, long long int>)':
ho_t5.cpp:94:9: warning: comparison of integer expressions of different signedness: 'llo' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
94 | while(i<tree3[no][0].size()){
| ~^~~~~~~~~~~~~~~~~~~~
ho_t5.cpp: In function 'std::pair<long long int, long long int> query3(llo, llo, llo, llo, llo, llo)':
ho_t5.cpp:142:17: warning: comparison of integer expressions of different signedness: 'llo' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
142 | if(low+(1<<j)<tree2[no].size()){
| ~~~~~~~~~~^~~~~~~~~~~~~~~~~
ho_t5.cpp: In function 'int solve(llo, llo)':
ho_t5.cpp:203:17: warning: comparison of integer expressions of different signedness: 'llo' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
203 | if(low+(1<<ii)<tt.size()){
| ~~~~~~~~~~~^~~~~~~~~~
ho_t5.cpp:218:10: warning: comparison of integer expressions of different signedness: 'llo' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
218 | if(low+1<tt.size()){
| ~~~~~^~~~~~~~~~
ho_t5.cpp: In function 'int main()':
ho_t5.cpp:255:15: warning: comparison of integer expressions of different signedness: 'llo' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
255 | for(llo i=0;i<tt.size();i++){
| ~^~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
40 ms |
94164 KB |
Output is correct |
| 2 |
Incorrect |
42 ms |
94412 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
40 ms |
94164 KB |
Output is correct |
| 2 |
Runtime error |
316 ms |
262144 KB |
Execution killed with signal 9 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
40 ms |
94164 KB |
Output is correct |
| 2 |
Runtime error |
320 ms |
262144 KB |
Execution killed with signal 9 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
280 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
40 ms |
94164 KB |
Output is correct |
| 2 |
Incorrect |
42 ms |
94412 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
