yukicoder : No.1921 Range LthKth Query

問題文の理解にちょっと手間取った。
https://yukicoder.me/problems/no/1921

問題

整数列Aと、整数K,Lが与えられる以下のクエリに答えよ。

整数列の部分列A[l...r]が指定される。
A[l...r]のうち、長さK以上の連続した部分列を考え、それぞれK番目に小さい値を抜き出したとする。
それらの数値の集合のうち、小さい方からL番目に小さいものを答えよ。

解法

全ての部分列について上記クエリの答えを列挙してしまおう。
g(l,r,m) := A[l...r]の部分列中、K番目の値がm以下のものの数
f(l,r) := A[l...r]に対する上記クエリの解
とすると、f(l,r)はg(l,r,m)が初めてLを超えるようなmとなる。
加えて、lを固定するとrが大きくなるたびにf(l,r)の値は小さくなる。

これを利用しよう。

A[i]のうち値を小さい順に有効化していったとする。
A[a...b]の区間内にm以下の値を有効化したときに、有効化した値がK個以上で揃った場合、l≦a≦b≦rである区間[l,r]に対し、g(l,r,m)に1加算されることになる。

g(l,r,m)の加算は、2次元BITを使い高速に計算できる。
また、g(l,r,m)が初めてLを超えたら、f(l,r)=mと定めよう。
あとは尺取り法の要領で、mが増すたびに小さいrに対しf(l,r)を定めていく。

int N,K,L;
int A[5525];
int dp[5525][5525];

template<class V,int MA> class BIT_2d {
public:
	V val[1<<MA][1<<MA];
	BIT_2d(){ZERO(val);};
	V total(int x,int y) {
		V s=0;
		for(int i=x+1;i>0;i-=i&-i) for(int j=y+1;j>0;j-=j&-j) s+=val[i-1][j-1];
		return s;
	}
	void update(int x,int y,V v) {
		for(int i=x+1;i<=1<<MA;i+=i&-i) for(int j=y+1;j<=1<<MA;j+=j&-j) val[i-1][j-1]+=v;
	}
};
BIT_2d<int,12> bit;

int R[5525];
int ret[2525][2525];
vector<pair<int,int>> cand[2525];

int get(int L,int R) {
	return bit.total(R+1,R+1)-bit.total(R+1,L)-bit.total(L,R+1)+bit.total(L,L);
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K>>L;
	FOR(i,N) cin>>A[i];
	
	MINUS(dp);
	FOR(x,N) {
		R[x]=N;
		multiset<int> S;
		for(y=x;y<N;y++) {
			S.insert(A[y]);
			if(S.size()>K) S.erase(S.find(*S.rbegin()));
			if(S.size()==K) {
				dp[x][y]=*S.rbegin();
				cand[dp[x][y]].push_back({x,y});
			}
		}
	}
	for(x=1;x<=N;x++) {
		FORR2(l,r,cand[x]) bit.update(l+1,r+1,1);
		FOR(i,N) {
			while(get(i,R[i]-1)>=L) {
				R[i]--;
				ret[i][R[i]]=x;
			}
		}
	}
	/*
	FOR(x,N) {
		for(y=x;y<N;y++) cout<<ret[x][y]<<" ";
		cout<<endl;
	}
	*/
	int Q;
	cin>>Q;
	while(Q--) {
		cin>>x>>y;
		cout<<ret[x-1][y-1]<<endl;
	}
	
}

まとめ

2次元BIT久々に使った。