CF840D Destiny

思路讲解

那我们还是要确认一下，我们的这个模版啊，问题不是很大，所以我们来用cf的题目测一下。

就改了一下这个query部分，其他都没动。

// u v 为node，l，r为区间，k为区间第k小（实际上来说，表示区间的是u，v。l，r为值域）
int query(int u,int v,int l,int r,int k){
	if(l==r){
		if(sum[v]-sum[u]>=k) return l;
		else return INF;
	}
	// 我们这样就知道了
	int lsum=sum[ls[v]]-sum[ls[u]];
	int mid=l+r>>1;
	int ans1=INF,ans2=INF;
	if(lsum>=k){
		ans1=query(ls[u],ls[v],l,mid,k);
	}
	if(ans1==INF && sum[rs[v]]-sum[rs[u]]>=k){
		ans2=query(rs[u],rs[v],mid+1,r,k);
	}
	// ans1= ans1==0?INF:ans1;ans2= ans2==0?INF:ans2;
	return min(ans1,ans2);
}

AC代码

https://codeforces.com/contest/840/submission/321605622

源代码

// Problem: D. Destiny
// Contest: Codeforces - Codeforces Round 429 (Div. 1)
// URL: https://codeforces.com/problemset/problem/840/D
// Memory Limit: 512 MB
// Time Limit: 2500 ms
// by znzryb
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define fi first
#define se second
#define pb push_back
#define SZ(a) ((int) a.size())
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define getFro(vec) (vec.empty()?0:vec.front())
#define getBac(vec) (vec.empty()?0:vec.front())
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define DEBUG(variable) \
    do { \
        std::cerr << #variable << ":"; \
        for (const auto& elem : variable) { \
            std::cerr << elem << " "; \
        } \
        std::cerr << "\n"; \
    } while (0)
#define uniVec(var) \
    do { \
        sort(var.begin(),var.end());\
        var.resize(unique(var.begin(),var.end())-var.begin());\
    } while (0)
#define debugN(var,N) \
	do{ \
		std::cerr<<#var<<":"; \
		FOR(i,1,N){ \
			std::cerr<<var[i]<<" "; \
		} \
		std::cerr<<"\n"; \
	}while(0)
#define debugMap(variable) \
    do { \
        std::cerr << #variable << ":\n"; \
        for (const auto& pair : variable) { \
            std::cerr << "  " << pair.first << " => " << pair.second << "\n"; \
        } \
        std::cerr << std::endl; \
    } while (0)
#define lson(var) (var<<1)
#define rson(var) ((var<<1)+1)
#define vecMxx(vec,x) (vec.end()-lower_bound(all(vec),x))	// vec中大于x的数有几个

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef __int128 i128;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr3;
typedef array<ll,2> arr2;
typedef double DB;
typedef long double LD;
typedef pair<DB,DB> pdd;
typedef pair<ll,bool> plb;
constexpr ll MAXN=static_cast<ll>(1e6)+10;
constexpr int INF=static_cast<int>(1e9)+3;
constexpr ll mod=static_cast<ll>(1e9)+7;
constexpr double eps=1e-8;

ll N,M,Q,X,K,lT,A[MAXN];
/*

*/
struct persisTree{	// 单点修改区间查询的主席树，处理静态区间第 k 小问题。
	// 由于太大了，该结构体只能声明与全局变量作用域
	// 测试 https://www.luogu.com.cn/record/218615977 （只测了单次数据）
	// maxn为点的数量，maxm为版本数量（在静态区间第 k 小问题中，和maxn一样）
	static const int maxn=static_cast<int>(5e5)+7,maxm=static_cast<int>(5e5)+7;
	static const int LOGmxm=20;		// 这个版本次数一般也不会超过2**20，也就是1048576
	static const int maxn4=maxn*4+LOGmxm*maxn;
	int ls[maxn4],rs[maxn4],L[maxn4],R[maxn4],root[maxm];
	int arr[maxn],sum[maxn4],li[maxn];
	int n=0,m=0,idx=1,Cver=0,len=0;
	// root为不同版本的根。L，R为左端点 右端点，ls rs 为左孩子 右孩子，arr为原数组。
	inline int initLi(int ln,int lm){	// 离散化操作
		idx=1,n=ln,m=lm,Cver=0;
		root[0]=1;	// 版本0的根是1
		for(int i=1;i<=n;++i){
			li[i]=arr[i];
		}
		sort(li+1,li+1+n);
		len=unique(li+1,li+1+n)-li-1;	// 这个len是超了一个的
		return len;
	}
	inline int kth(ll x){
		int ret=lower_bound(li+1,li+1+len,x)-li;
		return ret;
	}
	inline void clone(int node){
		++idx;
		L[idx]=L[node];
		R[idx]=R[node];
		sum[idx]=sum[node];
		ls[idx]=ls[node];
		rs[idx]=rs[node];
	}
	void build(int node,int l,int r){
		ls[node]=++idx;
		rs[node]=++idx;
		L[node]=l;
		R[node]=r;
		sum[node]=0;
		if(l==r) return;
		build(ls[node],l,((l+r)>>1));
		build(rs[node],(l+r>>1)+1,r);
	}
	// 处理静态区间第 k 小问题中，因为权值线段树，x=1
	// 注意，node调用时应该填入想要加的版本的根，即tr.root[versionNeddModify]
	void add(int node,int ver,int p,ll x){ 	
		clone(node);
		sum[idx]+=x;
		if(p==L[node] && p==R[node]){
			return;
		}
		// 如果当前遍历到的点是一个版本的根，那么现在的点idx就是目前这个版本的根
		if(root[ver]==node){	
			++Cver;
			root[Cver]=idx;
		}
		if(p>=L[ls[node]] && p<=R[ls[node]]){
			int nals=ls[idx];
			ls[idx]=idx+1;
			add(nals,ver,p,x);
		}else{
			int nars=rs[idx];
			rs[idx]=idx+1;
			add(nars,ver,p,x);
		}
	}
	// u v 为node，l，r为区间，k为区间第k小（实际上来说，表示区间的是u，v。l，r为值域）
	int query(int u,int v,int l,int r,int k){
		if(l==r){
			if(sum[v]-sum[u]>=k) return l;
			else return INF;
		}
		// 我们这样就知道了
		int lsum=sum[ls[v]]-sum[ls[u]];
		int mid=l+r>>1;
		int ans1=INF,ans2=INF;
		if(lsum>=k){
			ans1=query(ls[u],ls[v],l,mid,k);
		}
		if(ans1==INF && sum[rs[v]]-sum[rs[u]]>=k){
			ans2=query(rs[u],rs[v],mid+1,r,k);
		}
		// ans1= ans1==0?INF:ans1;ans2= ans2==0?INF:ans2;
		return min(ans1,ans2);
	}
};
persisTree tr;
inline void solve(){
	scanf("%lld%lld",&N,&M);
	FOR(i,1,N){
		scanf("%d",&tr.arr[i]);
	}
	int len=tr.initLi(N,N);
	tr.build(1,1,len);
	FOR(i,1,N){
		tr.add(tr.root[i-1],i-1,tr.kth(tr.arr[i]),1);
	}
	tr.li[0]=-1;
	FOR(_,1,M){
		int l,r,k;
		scanf("%d%d%d",&l,&r,&k);
		int mid=(r-l+1)/k+1;
		// int pos=tr.kth(mid);
		int ans=tr.query(tr.root[l-1],tr.root[r],1,len,mid);
		ans= ans==INF?-1:tr.li[ans];
		printf("%d\n",ans);
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	// cin>>lT;
	// while(lT--){
		// solve();
	// }
	solve();
	return 0;
}
/*
AC
https://codeforces.com/contest/840/submission/321605622
*/

心路历程（WA，TLE，MLE……）