이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
#define MAXN 300007
using namespace std;
const int bucket_sz=500;
int n,a[MAXN],q;
int br[MAXN],maxs,l,r,p[MAXN],len,bucket[MAXN],pos[MAXN],nxt[MAXN],pr[MAXN],w[MAXN];
long long ans,mult,sum,s[MAXN],res[MAXN];
struct Fenwick{
long long fenwick[MAXN];
void update(int x,long long val){
while(x<=maxs){
fenwick[x]+=val;
x+=(x & (-x));
}
}
long long getsum(int x){
long long res=0;
while(x>=1){
res+=fenwick[x];
x^=(x & (-x));
}
return res;
}
}pref,suff,sumpref,sumsuff;
struct query{
int l,r,id;
inline friend bool operator < (query fr,query sc){
if(bucket[fr.l]!=bucket[sc.l])return bucket[fr.l]<bucket[sc.l];
return fr.r<sc.r;
}
}qs[MAXN];
long long calc(int x){
return s[x] * ( pref.getsum(x-1)-sumpref.getsum(x-1)*(maxs-x+1) + suff.getsum(maxs-x)-sumsuff.getsum(maxs-x)*x );
}
void change(int x,long long val){
ans-=calc(x);
ans-=s[x]*(s[x]-1)/2+s[x];
s[x]+=val;
sumpref.update(x,val);
sumsuff.update(maxs-x+1,val);
pref.update(x,(maxs-x+2)*val);
suff.update(maxs-x+1,(x+1)*val);
ans+=calc(x);
ans+=s[x]*(s[x]-1)/2+s[x];
}
void add(int x){
br[x]++;
change(pos[x],1);
int z=pos[x];
while(nxt[z]!=z and br[w[nxt[z]]]<br[x]){
z=nxt[z];
}
int y=w[z];
if(x!=y){
change(pos[x],br[y]-br[x]);
change(pos[y],br[x]-br[y]);
swap(w[pos[x]],w[pos[y]]);
swap(pos[x],pos[y]);
}
}
void rem(int x){
br[x]--;
change(pos[x],-1);
int z=pos[x];
while(pr[z]!=0 and br[w[pr[z]]]>br[x]){
z=pr[z];
}
int y=w[z];
if(x!=y){
change(pos[x],br[y]-br[x]);
change(pos[y],br[x]-br[y]);
swap(w[pos[x]],w[pos[y]]);
swap(pos[x],pos[y]);
}
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n>>q;
for(int i=1;i<=n;i++){
cin>>a[i];
maxs=max(maxs,a[i]);
bucket[i]=i/bucket_sz;
}
for(int i=1;i<=maxs;i++)pos[i]=w[i]=i;
for(int i=1;i<=maxs;i++){
if(i<=maxs/2)nxt[i]=maxs-i+1;
else nxt[i]=maxs-i+2;
}
if(maxs%2==1)nxt[maxs/2+1]=maxs/2+1;
for(int i=1;i<=maxs;i++)pr[nxt[i]]=i;
for(int i=1;i<=q;i++){
cin>>qs[i].l>>qs[i].r;
qs[i].id=i;
}
sort(qs+1,qs+q+1);
l=1; r=0;
for(int i=1;i<=q;i++){
while(r<qs[i].r){
r++; add(a[r]);
}
while(l>qs[i].l){
l--; add(a[l]);
}
while(r>qs[i].r){
rem(a[r]); r--;
}
while(l<qs[i].l){
rem(a[l]); l++;
}
res[qs[i].id]=ans;
}
for(int i=1;i<=q;i++){
cout<<res[i]<<"\n";
}
return 0;
}
# | 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... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |