Lib/抽象化Mo
code:cpp
struct Mos_algo{
ll n;
function<void(ll&,ll,ll)> rplus;
function<void(ll&,ll,ll)> lminus;
function<void(ll&,ll,ll)> lplus;
function<void(ll&,ll,ll)> rminus;
vector<pair<ll,ll>> query = {};
vector<ll> ord = {};
vector<ll> ans = {};
ll q=0,bs=0,x=0,y=0,sigma=0;
void set(ll sx,ll sy,ll sv){
x = sx; y = sy; sigma = sv;
}
void insert(ll l,ll r){
query.push_back({l,r});
}
void fin(){
q = query.size();
bs = n / min< int >(n, sqrt(q));
ord.resize(q);
iota(ALL(ord),0);
ans.resize(q);
sort(ALL(ord),&(ll a,ll b){ int ablock = querya.first / bs, bblock = queryb.first / bs; if(ablock != bblock) return ablock < bblock;
return (ablock & 1) ? querya.second > queryb.second : querya.second < queryb.second; });
}
vector<ll> solve(){
fin();
rep(i,q){
while(y < tagr){
y++;
rplus(sigma,x,y);
}
while(x > tagl){
x--;
lminus(sigma,x,y);
}
while(x < tagl){
lplus(sigma,x,y);
x++;
}
while(y > tagr){
rminus(sigma,x,y);
y--;
}
}
return ans;
}
};
code:cpp
signed main(void){
ll n,q;
cin >> n >> q;
vector<ll> v(n+1,0);
vector<ll> ruiseki(n+1,0);
rep(i,n+1) ruisekii = vi; rep(i,n){
ruisekii+1 += ruisekii;//何故かただの累積和なのにいもす法って書いちゃう癖ある }
vector<ll> str(n+2,0);
vector<ll> stl(n+2,0);
rep(i,n+2) stli *= n+1-i; rep(i,n+1) stri+1 += stri; rep(i,n+1) stli+1 += stli; auto rplus = &(ll &sigma,ll x,ll y){sigma += (stry - strx-1) - (ruisekiy- ruisekix-1)*(x-1);}; auto lminus = &(ll &sigma,ll x,ll y){sigma += (stly - stlx-1) - (ruisekiy - ruisekix-1)*(n-y);}; auto lplus = &(ll &sigma,ll x,ll y){sigma -= (stly - stlx-1) - (ruisekiy - ruisekix-1)*(n-y);}; auto rminus = &(ll &sigma,ll x,ll y){sigma -= (stry - strx-1) - (ruisekiy- ruisekix-1)*(x-1);}; Mos_algo mo{n,rplus,lminus,lplus,rminus};
rep(i,q){
ll l,r;
cin >> l >> r;
mo.insert(l,r);
}
auto ans = mo.solve();
cout << join(ans,"\n") << endl;
}
なんかすごい遅くなったんだけどまあ実用面では大丈夫……だと思う
抽象度足りないみたいな話はある、そんときはそんとき