…とすること。 解法 Mo's Algorithmの要領で、グリッドを√Lの行ごとに分け、行ごとに左から右、右から左と操作しながら行内の点を通過すればよい。 int T,N,L; int X[202020],Y[202020]; const int DI=300; void solve() { int i,j,k,l,r,x,y; string s; cin>>T; while(T--) { cin>>N>>L; vector<vector<int>> V; int span=…

…値を求めよ。 解法 Mo's Algorithmを回すだけでも間に合う。 int N,Q; int A[303030],pos[303030]; int PL[303030],PR[303030]; int L[1303030],R[1303030]; int ret[1303030]; const int DI=550; int S[303030]; int B[303030]; void solve() { int i,j,k,l,r,x,y; string s; sca…

…O(√N)で済む。 Mo's Algorithmの応用で、(U,V)の訪問順を並べ替え、U,Vをそれぞれ走査していこう。 int N; int V[202020]; vector<int> E[202020]; int P[202020]; //親 int S[202020]; //subtreeサイズ int G[202020]; //グループ //グループ毎の属性 int L[202020],R[202020]; //葉と根 const int DI=500; int C…

…クエリな問題なので、Mo's Algorithmは使えない。 T[i]を、A[0]～A[i-1]のうち奇数回現れるものを含む永続Trieとする。 T[L-1]とT[R]を同時に探索し、片方にしか現れない最小要素を求めればよい。なお、Trieにおいては各整数値に対応するハッシュ値を割り当てそのxorをとることで、Subtree内に現れる整数の要約を作ることができる。 これにより、Trieのノードの内容が等しいかどうか高確率で正しく判定できる。 int N,Q; int A[20…

…でクエリを並べ替え、Mo's Algorithmで処理していこう。 int T; int N[202020],M[202020]; vector<pair<int,int>> ev[505]; ll ret[202020]; const ll mo=998244353; ll comb(ll N_, ll C_) { const int NUM_=1430001; static ll fact[NUM_+1],factr[NUM_+1],inv[NUM_+1]; if (fa…

…和を求めよ。 解法 Mo's Algorithmで解ける。 ACで区切られたWAの回数をdequeで管理し、AC/WAの数をカウントしよう。 ただdequeは処理が重くTLEするので、以下では長い配列を区切ってdeque的な使い方をしている。 int N,M,Q; int P[202020],S[202020]; int L[202020],R[202020],ac[202020],wa[202020]; int PL[202020],PR[202020]; int num[…

…新できる。 そこで、Mo's Algorithmでクエリを並べ替えて処理すればよい。 int N,Q; int A[202020]; ll C[202020]; int L[202020],R[202020]; ll ret[202020]; void solve() { int i,j,k,l,r,x,y; string s; cin>>N>>Q; FOR(i,N) cin>>A[i]; vector<vector<int>> E; FOR(i,Q) { cin>>L[i]…

…T個のテストケースをMo's Algorithmの要領で並べ替え、f(n,m)を順次求めて行こう。 int T; int N[202020],M[202020]; const ll mo=998244353; ll ret[202020]; ll comb(ll N_, ll C_) { const int NUM_=400001; static ll fact[NUM_+1],factr[NUM_+1],inv[NUM_+1]; if (fact[0]==0) { inv[…

… あとは各区間に対しMo's Algorithmで類似度を適宜求めて行けばよい。 ll A[101010],B[101010],C[101010]; template<class V, int ME> class BIT { public: V bit[1<<ME]; V operator()(int e) {if(e<0) return 0;V s=0;e++;while(e) s+=bit[e-1],e-=e&-e; return s;} void add(int e,V…

…う。なお、自分は最初Mo's Algorithmの適用を考えたが、これだとちょっとTLに間に合わなかった。 vector<int> ev[303030]; deque<int> D[303030]; template<class V, int ME> class BIT { public: V bit[1<<ME]; V operator()(int e) {if(e<0) return 0;V s=0;e++;while(e) s+=bit[e-1],e-=e&-e; re…

…時間と添え字の二軸でMo's Algorithmを使っていくとよい。K通りの値の数え方だが、頻度を小さい順に格納した数列を管理しよう。 頻度の組み合わせは√N通りなので、小さい方の頻度を総当たりしても間に合う。 int N,M; int A[201010]; vector<vector<int>> event; vector<vector<int>> update; int ret[201010]; const int DI=2222; int C[201010]; int …

…先読みして並べ替え、Mo's algorithmを適用しよう。 int N,Q; int A[101010]; int L[1010101],R[1010101]; vector<pair<int,int>> cand[1010]; int ret[1010101]; int vis[101010]; const int DI=330; void solve() { int i,j,k,l,r,x,y; string s; cin>>N; FOR(i,N) cin>>A[i]…

…。 解法 以下では、Mo's Algorithmで解いている。 区間内における各値の登場を数え上げ、1回以上登場した値の種類を適宜更新している。 ただこれはO(N√N+Q)程度必要で効率が悪い。 実際ACはできるものの2秒近くかかっている。別解としてはBITによる区間和を使ったものかな。 ある値が初めて登場する位置に1を足しこむことで、右端が決まったときにそこまでに現れる値の種類をO(N)で数え上げられるようにする。 左端を走査しつつ各クエリを捌いていき、左端からはみ出た値に…

…(N^2)かかるが、Mo's Algorithmを使うとO(N√NlogN)で済む。 先端・末尾が伸縮する数列における中央値は、値の下半分と上半分を格納する2つのmultisetを使うと容易に求められる。 int N; int A[10101]; map<int,int> T[101010]; vector<pair<int,int>> E[101]; multiset<int> X,Y; void add(int v) { X.insert(v); Y.insert(*X.…

…きる。 上端と下端はMo's Algorithmを使いながら1ずつずらしていくとよい。縦横を逆にするとR'も同様に求められる。 template<class V, int ME> class BIT { public: V bit[1<<ME]; V operator()(int e) {if(e<0) return 0;V s=0;e++;while(e) s+=bit[e-1],e-=e&-e; return s;} void add(int e,V v) { e++; …

… それ以外のケースはMo's Algorithmでゴリ押した。 Mo's Algorithmで区間内に存在する整数値の集合をbitsetで保持しよう。 gccの__builtin_clzllで64bit値の最上位bitを得られるので、これを使い高速に各64値毎の最大値を求めていく。 template<class V,int NV> class SegTree_1 { public: vector<V> val; static V const def=0; V comp(V l…

…覚えておけば、あとはMo's Algorithmで平方分割するだけ。 O(N^1.5)程度のになるので、Nの上限10^6では通らないかと思ったら通ってしまった。想定解法はBITを使う方法だそうで。 int N; int nex[1010101]; int pre[1010101]; int Q,L[1010101],R[1010101],ret[1010101]; vector<pair<int,int>> E[1015]; void solve() { int i,j,k,…

…しかし自分はわざわざMo's Algorithmで解いてしまった。 class SCC_BI { public: static const int MV = 310000; int NV,time; vector<vector<int> > E; vector<int> ord,llink,inin; stack<int> roots,S; vector<int> M; //point to group vector<int> ART; // out vector<vecto…

…algorithm Mo's Algorithm 28 Segment trees revisited セグメントツリーの応用的な話題 28.1 Lazy propagation 遅延伝搬処理・多項式の更新 28.2 Dynamic trees 動的木・永続セグメントツリー 28.3 Data structures セグメントツリーのノードにさらに複雑な値を載せる 28.4 Two-dimensionality 二次元セグメントツリー 29 Geometry 幾何 29.1 …

…通りあるか。 解法 Mo's Algorithmで解く。 まず、各区間の左端A[i]に対し、同じ数字を複数含まない最大の右端B[i]を求めておこう。あとはMo's Algorithmの要領で、左右の端を動かしつつ、内部に含まれる条件を満たす区間の数を求める。 区間内の要素をそれぞれ左端iとする場合、R＜B[i]であるなら区間Rを右に動かしたとき、条件を満たす区間は1つ増加する。 この条件をもとに、クエリ区間内に収まらない右端の個数と、条件を満たす部分区間の数をそれぞれ更新して…

…求めておこう。あとはMo's Algorithmで解いていく。 まずS[i]を、map等使い同じ値同士分類しよう。keyがS[i]、valueがiの昇順vectorとなるようにしておく。 あとは[L...R]に対する解の値から、前後1つ伸ばすか減らす場合の解の増減分を求めればよい。 例えば[L...R]から[L...(R+1)]になるとき、S[R+1]-S[x]=kとなるようなk∈[L..R]の数だけ解は増加する。 これはkeyを(S[R+1]-k)とするvalueのvect…

…コストが小さいため、Mo's algorithmで解くことができる。なお、区間の増減の際複数の素因数に対し処理を行う必要があるので、Mo's algorithmを適用するだけだとまだちょっと重くTLEする。 Editorialでは、小さな素因数に対しては区間に対する素因数の指数の総和を前処理することで高速化している。 以下のコードではこのアプローチを取らず、同一の指数の複数回加減算をまとめたり、インラインアセンブラによる除算の高速化で無理やり通している。 int N,Q; l…

…。 解法 平方分割でMo's Algorithmして解く。 区間の長さを1変えるとき、2要素の最大値の総和は以下のように変化する。区間を1伸ばし、値xが追加される場合、 xとx未満の要素が選ばれると考えると、x未満の要素の数だけ、2xが加算される。(2xは選び方が順不動なため) xとx以上の要素が選ばれると考えると、x以上の要素の数だけ、2*その要素が加算される。(2倍は選び方が順不動なため) 言い換えると、x以上の要素の総和の2倍が加算される。 自身が2回選ばれる場合、xが…

…よ。 解法 想定解はMo's Algorithmなのだが…。 愚直にO(N^2)通りf(A[L],A[R])を列挙しても間に合ってしまうようだ。 int N,M; int A[50050],X[50500]; int L[50050],R[50500]; int XX[1010101]; int ma[50505]; int ret[50505]; void solve() { int i,j,k,l,r,x,y; string s; for(i=1;i<=1000000;i…

…は定番のテクがある(Mo's Algorithmと呼ばれているらしい?)。クエリをfloor(L/√N)昇順でfloor(L/√N)が一致するものはR順に並べ替えよう。 すると１回のクエリあたり区間の左端Lを動かす量は平均O(√N)となることが期待できる。 また区間の右端は基本的に右に動かすだけで、前のクエリと比べfloor(L/√N)が異なるときだけ左に戻すので、左に戻す回数はO(√N)であることが期待できる。 よってLもRも動かす回数はO(N√N)程度動かせばよい。 in…