結果
問題 | No.1270 Range Arrange Query |
ユーザー |
![]() |
提出日時 | 2020-10-24 00:57:38 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2,537 ms / 7,000 ms |
コード長 | 7,735 bytes |
コンパイル時間 | 2,905 ms |
コンパイル使用メモリ | 226,924 KB |
最終ジャッジ日時 | 2025-01-15 14:48:38 |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 15 |
ソースコード
#include<bits/stdc++.h>using namespace std;#define ALL(x) begin(x),end(x)#define rep(i,n) for(int i=0;i<(n);i++)#define debug(v) cout<<#v<<":";for(auto x:v){cout<<x<<' ';}cout<<endl;#define mod 1000000007using ll=long long;const int INF=1000000000;const ll LINF=1001002003004005006ll;int dx[]={1,0,-1,0},dy[]={0,1,0,-1};// ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}template<class T>bool chmax(T &a,const T &b){if(a<b){a=b;return true;}return false;}template<class T>bool chmin(T &a,const T &b){if(b<a){a=b;return true;}return false;}#pragma GCC target("avx2")#pragma GCC optimize("O3")#pragma GCC optimize("unroll-loops")struct IOSetup{IOSetup(){cin.tie(0);ios::sync_with_stdio(0);cout<<fixed<<setprecision(12);}} iosetup;template<typename T>ostream &operator<<(ostream &os,const vector<T>&v){for(int i=0;i<(int)v.size();i++) os<<v[i]<<(i+1==(int)v.size()?"":" ");return os;}template<typename T>istream &operator>>(istream &is,vector<T>&v){for(T &x:v)is>>x;return is;}struct Mo{using F=function<void(int)>;int n,idx,ql,qr;vector<pair<int,int>> query;vector<int> ord;// [l,r)// add_left : l-1を足す, add_right : rを足す// erase_left: lを消す, erase_right: r-1を消すF add_left,add_right,erase_left,erase_right;Mo(int n,F add_left,F add_right,F erase_left,F erase_right):n(n),idx(0),ql(0),qr(0),add_left(add_left),add_right(add_right),erase_left(erase_left),erase_right(erase_right){}void add(int l,int r){query.emplace_back(l,r);}void build(){int q=(int)query.size();int bs=n/min(n,int(sqrt(q)));// 左端のブロックでソート// 左端のブロックが同じなら右端でソートord.resize(q);iota(begin(ord),end(ord),0);sort(begin(ord),end(ord),[&](int a,int b){int al=query[a].first/bs,bl=query[b].first/bs;if(al!=bl) return al<bl;// 偶奇で始点を左右に振ると動きに無駄がないif(al&1) return query[a].second>query[b].second;return query[a].second<query[b].second;});}// 1個クエリを進め,処理したクエリのindexを返す// processが終わってから結果を格納すること// ans[process()]=res;とかはヤバイので注意.実装がよくないint process(){if(idx>=(int)ord.size()) return -1;int now=ord[idx++];while(ql>query[now].first) add_left(--ql);while(qr<query[now].second) add_right(qr++);while(ql<query[now].first) erase_left(ql++);while(qr>query[now].second) erase_right(--qr);return now;}};template<typename Monoid>struct SegmentTree{using F=function<Monoid(Monoid,Monoid)>;int sz;vector<Monoid> seg;const F f;const Monoid gen;SegmentTree(int n,const F f,const Monoid &gen):f(f),gen(gen){sz=1;while(sz<n)sz<<=1;seg.assign(2*sz,gen);}void set(int k,const Monoid &x){seg[k+sz]=x;}void build(){for(int k=sz-1;k>0;k--) seg[k]=f(seg[2*k],seg[2*k+1]);}void update(int k,const Monoid &x){k+=sz;seg[k]=x;while(k>>=1) seg[k]=f(seg[2*k],seg[2*k+1]);}// [a,b)Monoid query(int a,int b){Monoid L=gen,R=gen;for(a+=sz,b+=sz;a<b;a>>=1,b>>=1){if(a&1) L=f(L,seg[a++]);if(b&1) R=f(seg[--b],R);}return f(L,R);}Monoid operator[](const int &k)const {return seg[k+sz];}};template<typename Monoid, typename OperatorMonoid=Monoid>struct LazySegmentTree{using F=function<Monoid(Monoid,Monoid)>;using G=function<Monoid(Monoid,OperatorMonoid)>;using H=function<OperatorMonoid(OperatorMonoid,OperatorMonoid)>;int sz,height;vector<Monoid> data;vector<OperatorMonoid> lazy;const F f;const G g;const H h;const Monoid M1;const OperatorMonoid OM0;LazySegmentTree(int n,const F f,const G g,const H h,const Monoid &M1,const OperatorMonoid OM0): f(f),g(g),h(h),M1(M1),OM0(OM0) {sz=1;height=0;while(sz<n) sz<<=1,height++;data.assign(2*sz,M1);lazy.assign(2*sz,OM0);}void set(int k,const Monoid &x){data[k+sz]=x;}void build(){for(int k=sz-1;k>0;k--) data[k]=f(data[2*k+0],data[2*k+1]);}inline void propagate(int k){if(lazy[k]!=OM0){lazy[2*k+0]=h(lazy[2*k+0],lazy[k]);lazy[2*k+1]=h(lazy[2*k+1],lazy[k]);data[k]=reflect(k);lazy[k]=OM0;}}inline Monoid reflect(int k){return lazy[k]==OM0?data[k]:g(data[k],lazy[k]);}inline void recalc(int k){while(k>>=1)data[k]=f(reflect(2*k+0),reflect(2*k+1));}inline void thrust(int k){for(int i=height;i>0;i--) propagate(k>>i);}void update(int a,int b,const OperatorMonoid &x){if(a>=b) return ;thrust(a+=sz);thrust(b+=sz-1);for(int l=a,r=b+1;l<r;l>>=1,r>>=1){if(l&1) lazy[l]=h(lazy[l],x),l++;if(r&1) --r,lazy[r]=h(lazy[r],x);}recalc(a);recalc(b);}Monoid query(int a,int b){thrust(a+=sz);thrust(b+=sz-1);Monoid L=M1,R=M1;for(int l=a,r=b+1;l<r;l>>=1,r>>=1){if(l&1) L=f(L,reflect(l++));if(r&1) R=f(reflect(--r),R);}return f(L,R);}Monoid operator[](const int &k){return query(k,k+1);}};// range add range minusing M=ll;using OM=ll;const M M1=LINF;const OM OM0=0;M segf(M a,M b){return (a<b?a:b);}M segg(M a,OM b){return a+b;}OM segh(OM a,OM b){return a+b;}signed main(){int n,q;cin>>n>>q;vector<int> a(n);rep(i,n){cin>>a[i];a[i]--;}auto segfunc=[&](int lhs,int rhs){return lhs+rhs;};SegmentTree<int> seg_l(n,segfunc,0),seg_r(n,segfunc,0);auto Q=[&](int t){return seg_l.query(t+1,n)+seg_r.query(0,t);};LazySegmentTree<ll,ll> sb(n,segf,segg,segh,M1,OM0);seg_l.build();seg_r.build();ll inv=0;// build_rvector<int> cnt(n,0);{for(auto &x:a){cnt[x]++;inv+=seg_r.query(x+1,n);seg_r.update(x,cnt[x]);}}rep(i,n)sb.set(i,Q(i));sb.build();auto add_l=[&](int x){inv-=seg_l.query(a[x]+1,n);inv-=seg_r.query(0,a[x]);seg_l.update(a[x],seg_l[a[x]]-1);sb.update(0,a[x],-1);};auto add_r=[&](int x){inv-=seg_l.query(a[x]+1,n);inv-=seg_r.query(0,a[x]);seg_r.update(a[x],seg_r[a[x]]-1);sb.update(a[x]+1,n,-1);};auto erase_l=[&](int x){inv+=seg_l.query(a[x]+1,n);inv+=seg_r.query(0,a[x]);seg_l.update(a[x],seg_l[a[x]]+1);sb.update(0,a[x],1);};auto erase_r=[&](int x){inv+=seg_l.query(a[x]+1,n);inv+=seg_r.query(0,a[x]);seg_r.update(a[x],seg_r[a[x]]+1);sb.update(a[x]+1,n,1);};Mo mo(n,add_l,add_r,erase_l,erase_r);vector<ll> ans(q);vector<int> l(q),r(q);rep(i,q){cin>>l[i]>>r[i];l[i]--;mo.add(l[i],r[i]);}mo.build();rep(i,q){int j=mo.process();// shake();ans[j]=sb.query(0,n)*(r[j]-l[j]);ans[j]+=inv;// cout<<l[i]<<" ~ "<<r[i]<<" : "<<sb.query(0,n)<<" , "<<inv<<endl;// rep(k,n) cout<<sb[k]<<" ";// cout<<endl;}for(auto &x:ans) cout<<x<<"\n";return 0;}