6 条题解

  • 1
    @ 2026-8-3 9:33:09

    热知识：scy 的题解中注释打错位置了，以下是正确的注释：

    #include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#define ll long long
using namespace std;
using namespace __gnu_pbds;

// 定义 ordered_set，底层为红黑树，不允许重复元素


typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;

int main()
{
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int n,q;
	cin>>n>>q;
	ordered_set s;
	for(int i=1,x;i<=n;i++)cin>>x,s.insert(x);
	while(q--)
	{
		int t,x;cin>>t>>x;
		if(t==0)s.insert(x);
		else if(t==1)s.erase(x);
		else if(t==2)
		{
			if(x>(int)s.size()) cout<< -1 <<'\n';
			else cout<< *s.find_by_order(x-1) << '\n';
      //find_by_order是0_based，也就是排序后第一个数的下标为0，所以要-1
		}
		else if(t==3)
		{
			int ans=(int)(s.order_of_key(x+1));
			cout<<ans<<endl;
      // order_of_key(x) 返回严格小于 x 的个数，所以 <= x 的个数是 order_of_key(x + 1)
		}
		else if(t==4)
		{
			auto it=s.upper_bound(x);
			if(it==s.begin())cout<<-1<<'\n';
			else cout<< *(--it)<<'\n';
		}
		else if(t==5)
		{
			auto it=s.lower_bound(x);
			if(it==s.end())cout<<-1<<'\n';
			else cout<< *it <<'\n';
		}
	}
	return 0;
}
  • 0
    @ 2026-8-2 21:02:16

    在 C++ 中，标准库的 std::set 虽然支持插入、删除以及通过 lower_bound / upper_bound 查询前驱和后继，但不支持 O(log⁡N)O(\log N) 复杂度的“查询第 kk 小”和“查询小于等于 xx 的个数”。如果强行使用 std::set 遍历来实现操作 2 和 3，时间复杂度会退化为 O(N)O(N)，导致超时。

    解决方案： 在 C++ 竞赛中，解决这类“有序集合”问题的标准做法是使用 GNU PBDS（Policy-Based Data Structures）库中的 tree。它通常被封装为 ordered_set，底层基于红黑树，接口与 std::set 几乎完全相同，但额外提供了两个强大的函数：

    • find_by_order(k)：返回第 kk 小的元素（0-based）。
    • order_of_key(x)：返回严格小于 xx 的元素个数。

    ordered_set 解法：

    必背

    #include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#define int long long
using namespace std;
using namespace __gnu_pbds;

// 定义 ordered_set，底层为红黑树，不允许重复元素


typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;

signed main()
{
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int n,q;
	cin>>n>>q;
	ordered_set s;
	for(int i=1,x;i<=n;i++)cin>>x,s.insert(x);
	while(q--)
	{
		int t,x;cin>>t>>x;
		if(t==0)s.insert(x);
		else if(t==1)s.erase(x);
		else if(t==2)
		{
			if(x>(int)s.size()) cout<< -1 <<'\n';
			else cout<< *s.find_by_order(x-1) << '\n';// order_of_key(x) 返回严格小于 x 的个数，所以 <= x 的个数是 order_of_key(x + 1)
		}
		else if(t==4)
		{
			auto it=s.upper_bound(x);
			if(it==s.begin())cout<<-1<<'\n';
			else cout<< *(--it)<<'\n';
		}
		else if(t==5)
		{
			auto it=s.lower_bound(x);
			if(it==s.end())cout<<-1<<'\n';
			else cout<< *it <<'\n';
		}
	}
	return 0;
}

    细节说明：

    1. 头文件：需要额外包含 <ext/pb_ds/assoc_container.hpp> 和 <ext/pb_ds/tree_policy.hpp>，并引入 __gnu_pbds 命名空间。
    2. 去重特性：null_type 和 less<int> 的组合使得该 tree 表现为一个不允许重复元素的集合（即 set）。如果插入已存在的元素或擦除不存在的元素，它会自动忽略，完美契合题目要求。
    3. 前驱与后继：
      • 操作 4（<= x 的最大值）：使用 upper_bound(x) 找到第一个 > x 的元素，它的前一个元素即为所求。如果它指向 begin()，说明没有 <= x 的元素。
      • 操作 5（>= x 的最小值）：使用 lower_bound(x) 找到第一个 >= x 的元素。如果它指向 end()，说明没有 >= x 的元素。
    4. 兼容性：该解法依赖 GCC 编译器的 PBDS 库，在绝大多数 OI/ACM 评测机（如洛谷、Codeforces、AtCoder 等）上均可直接编译运行。

    用set超时52分程序：

    #include <bits/stdc++.h>
#define int long long
using namespace std;

signed main() {
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int n, q;
    cin >> n >> q;
    set<int> s;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        s.insert(x);
    }
    for (int i = 0; i < q; i++) {
        int t, x;
        cin >> t >> x;
        if (t == 0) { // 插入 x（set自动去重）
            s.insert(x);
        } else if (t == 1) { // 删除 x（若不存在则不操作）
            s.erase(x);
        } else if (t == 2) { // 查询第 x 小的元素 (1-based)
            if (x > (int)s.size()) {
                cout << -1 << '\n';
            } else {
                auto it = s.begin();
                advance(it, x - 1); // 注意：此处复杂度为 O(N)
                cout << *it << '\n';
            }
        } else if (t == 3) { // 查询 <= x 的元素个数
            auto it = s.upper_bound(x);
            cout << distance(s.begin(), it) << '\n'; // 注意：此处复杂度为 O(N)
        } else if (t == 4) { // 查询 <= x 的最大元素 (前驱)
            auto it = s.upper_bound(x);
            if (it == s.begin()) {
                cout << -1 << '\n';
            } else {
                it--;
                cout << *it << '\n';
            }
        } else if (t == 5) { // 查询 >= x 的最小元素 (后继)
            auto it = s.lower_bound(x);
            if (it == s.end()) {
                cout << -1 << '\n';
            } else {
                cout << *it << '\n';
            }
        }
    }
    return 0;
}

    细节说明与复杂度警告：

    1. 自动去重与删除：std::set 天然保证元素唯一，因此操作 0 直接 insert 即可；操作 1 直接 erase(x)，如果 x 不存在，set 会自动忽略，不会报错。
    2. 操作 4 和 5（前驱与后继）：使用 upper_bound 和 lower_bound 可以在 O(log⁡N)O(\log N) 时间内完成，这是 set 的强项。
    3. 操作 2 和 3 的 O(N)O(N) 复杂度警告：
      • std::set 底层是红黑树，其迭代器是双向迭代器，不支持随机访问。
      • 因此，std::advance(it, k) 只能一步步向后移动，std::distance(first, last) 也只能一步步向前计数。这两者的时间复杂度均为 O(N)O(N)。
      • 在 Q≤5×105Q \le 5 \times 10^5 的数据规模下，如果多次执行操作 2 或 3，必然会导致超时（TLE）。

    补充建议：如果在实际比赛中遇到此题且必须使用纯 STL（不使用 PBDS），通常的解法是结合树状数组/线段树与离散化，或者使用你之前熟悉的分块思想（将值域分块）来维护，从而将操作 2 和 3 的复杂度降至 O(Nlog⁡N)O(\sqrt{N} \log N) 或 O(log⁡2N)O(\log^2 N)。单纯依赖 std::set 无法在底层结构上突破 O(N)O(N) 的限制。

    • 0
      @ 2026-8-2 11:02:37

      用平衡树写了篇题解

      #include<bits/stdc++.h>
using namespace std;
#define lc(p) tr[p].ls
#define rc(p) tr[p].rs
const int M=1e6+10;//注意此处M为N+Q 
map<int,bool>vv;//vv记录是否在S中 
struct node
{
	int ls,rs,siz,val,rnd;
}tr[M];
int trlen,rt;
int newd(int v)
{
	tr[++trlen]={0,0,1,v,rand()};
	return  trlen;
}
void pushup(int p)
{
	tr[p].siz=tr[lc(p)].siz+tr[rc(p)].siz+1;
}
void split(int p,int v,int &x,int &y)
{
	if(!p)
	{
		x=y=0;
		return ;
	}
	if(tr[p].val<=v)
	{
		x=p;
		split(rc(p),v,rc(x),y);
	}
	else
	{
		y=p;
		split(lc(p),v,x,lc(y));
	}
	pushup(p);
}
int merge(int x,int y)
{
	if(!x||!y)
	{
		return x+y;
	}
	if(tr[x].rnd<tr[y].rnd)
	{
		rc(x)=merge(rc(x),y);
		pushup(x);
		return x;
	}
	else
	{
		lc(y)=merge(x,lc(y));
		pushup(y);
		return y;
	}
}
void ins(int v)
{
	int x,y;
	split(rt,v-1,x,y);
	rt=merge(merge(x,newd(v)),y);
}
void del(int v)
{
	int x,y,z;
	split(rt,v-1,x,y);
	split(y,v,y,z);
	rt=merge(merge(x,merge(lc(y),rc(y))),z);
}
int getrnd(int v)
{
	int x,y;
	split(rt,v-1,x,y);
	int res=tr[x].siz+vv[v];
	rt=merge(x,y);
	return res;
}
int getval(int p,int k)
{
	if(tr[lc(p)].siz+1==k)
	{
		return tr[p].val;
	}
	if(k<=tr[lc(p)].siz)
	{
		return getval(lc(p),k);
	}
	else
	{
		return getval(rc(p),k-tr[lc(p)].siz-1);
	}
}
int getpre(int v)
{
	int x,y;
	split(rt,v,x,y);
	int r=tr[x].siz;
	int res=getval(x,r);
	rt=merge(x,y);
	return res;
}
int getnxt(int v)
{
	int x,y;
	split(rt,v-1,x,y);
	int res=getval(y,1);
	rt=merge(x,y);
	return res;
}//前面为平衡树板子 
int main()
{
	int n,m;
	scanf("%d%d",&n,&m);
	int sum=n;//sum为当前S的总数 
	for(int i=1;i<=n;i++)
	{
		int x;
		scanf("%d",&x);
		ins(x);
		vv[x]=1;
	}
	while(m--)
	{
		int op,x;
		scanf("%d%d",&op,&x);
		op++;
		if(op==1)
		{
			if(vv[x])
			{
				continue;
			}
			ins(x);
			vv[x]=1;
			sum++;
		}
		else if(op==2)
		{
			if(!vv[x])
			{
				continue;
			}
			del(x);
			vv[x]=0;
			sum--;
		}
		else if(op==3)
		{
			if(sum<x)
			{
				printf("-1\n");
				continue;
			}
			printf("%d\n",getval(rt,x));
		}
		else if(op==4)
		{
			if(!sum)
			{
				printf("0\n");
				continue;
			}
			printf("%d\n",getrnd(x));
		}
		else if(op==5)
		{
			if(!sum||x<getval(rt,1))//S中最小的数 
			{
				printf("-1\n");
				continue;
			}
			printf("%d\n",getpre(x));
		}
		else
		{
			if(!sum||x>getval(rt,sum))//S中最大的数 
			{
				printf("-1\n");
				continue;
			}
			printf("%d\n",getnxt(x));
		}
	}
	return 0;
}
      • 0
        @ 2025-12-18 16:09:23

        pb_ds 解法（目前最优解）:

        #include<bits/stdc++.h>
#include<bits/extc++.h>
using namespace std;
using namespace __gnu_pbds;
tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>s;
int main()
{
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int n,q;cin>>n>>q;
	for(int i=1,x;i<=n;i++)cin>>x,s.insert(x);
	while(q--)
	{
		int op,x;cin>>op>>x;
		if(op==0)s.insert(x);
		if(op==1)s.erase(x);
		if(op==2)
		{
			auto it=s.find_by_order(x-1);
			if(it==s.end())cout<<-1<<'\n';
			else cout<<*it<<'\n';
		}
		if(op==3)
		{
			auto it=s.upper_bound(x);
			if(it==s.end())cout<<s.size()<<'\n';
			else
			{
				int num=*it,id=s.order_of_key(num);
				cout<<id<<'\n';
			}
		}
		if(op==4)
		{
			auto it=s.upper_bound(x);
			if(it==s.begin())cout<<-1<<'\n';
			else it--,cout<<*it<<'\n';
		}
		if(op==5)
		{
			auto it=s.lower_bound(x);
			if(it==s.end())cout<<-1<<'\n';
			else cout<<*it<<'\n';
		}
	}
	return 0;
}
        • 0
          @ 2025-12-7 16:33:57 
          #include<bits/stdc++.h>
using namespace std;
#define int long long
#define N 100000
#define pb push_back
set<int>se[N];
int n,q;
int B,nB;
int sum;
vector<int>a,lsh;
vector<pair<int,int> >query;

unordered_map<int,int>mp;

int getid(int x){
	return (int)(upper_bound(lsh.begin(),lsh.end(),x)-lsh.begin()-1);
}

void ins(int x){
	x=getid(x);
	int k=x/B;
	auto &s=se[k];
	if(!s.count(x))
		s.insert(x),sum++;
}
void era(int x){
	int xx=getid(x);
	if(lsh[xx]==x)x=xx;
	else return;
	int k=x/B;
	auto &s=se[k];
	if(s.count(x))
		s.erase(x),sum--;
}
int kth(int k){
	if(k<1||k>sum)return -1;
	for(int i=0;i<nB;i++){
		int siz=se[i].size();
		if(k>siz)k-=siz;
		else{
			auto it=se[i].begin();
			advance(it,k-1);
			return *it;
		}
	}
	return -1;
}
int lessnum(int x){
	x=getid(x);
	int k=x/B;
	auto &s=se[k];
	int cnt=0;
	for(int i=0;i<k;i++)cnt+=se[i].size();
	auto it=s.upper_bound(x);
	cnt+=distance(s.begin(),it);
	return cnt;
}
int smaller(int x){
	x=getid(x);
	int k=x/B;
	auto &s=se[k];
	auto it=s.upper_bound(x);
	if(it!=s.begin()){
		return *--it;
	}
	for(int i=k-1;i>=0;i--){
		if(se[i].size())return *se[i].rbegin();
	}
	return -1;
}
int larger(int x){
	x=lower_bound(lsh.begin(),lsh.end(),x)-lsh.begin();
	if(x==lsh.size())return -1;
	int k=x/B;
	auto &s=se[k];
	auto it=s.lower_bound(x);
	if(it!=s.end()){
		return *it;
	}
	for(int i=k+1;i<nB;i++){
		if(se[i].size())return *se[i].begin();
	}
	return -1;
}

void init(){
	sum=0;
	for(int x:a){
		x=getid(x);
		int k=x/B;
		auto &s=se[k];
		if(!s.count(x)){
			s.insert(x);sum++;
		}
	}
	for(int x:lsh){
		mp[getid(x)]=x;
	}
	mp[-1]=-1;
}
signed main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>n>>q;
	for(int i=1;i<=n;i++){
		int x;cin>>x;
		a.pb(x);lsh.pb(x);
	}
	
	for(int i=1;i<=q;i++){
		int op,x;cin>>op>>x;
		query.pb({op,x});
		if(op==0)lsh.pb(x);
	}
	sort(lsh.begin(),lsh.end());
	lsh.erase(unique(lsh.begin(),lsh.end()),lsh.end());
	n=lsh.size();
	
	B=500;
	nB=(n+B-1)/B;
	
	init();
	
	if(n==0){
		for(auto i:query){
			int op=i.first,x=i.second;
			
			switch(op){
				case 2:
					cout<<"-1\n";
					break;
				case 3:
					cout<<"0\n";
					break;
				case 4:
					cout<<"-1\n";
					break;
				case 5:
					cout<<"-1\n";
					break;
			}
		}
		
		return 0;
	}
	
	for(auto i:query){
		int op=i.first,x=i.second;
		switch(op){
			case 0:
				ins(x);
				break;
			case 1:
				era(x);
				break;
			case 2:
				cout<<mp[kth(x)]<<'\n';
				break;
			case 3:
				cout<<lessnum(x)<<'\n';
				break;
			case 4:
				cout<<mp[smaller(x)]<<'\n';
				break;
			case 5:
				cout<<mp[larger(x)]<<'\n';
				break;
		}
	}
	
	return 0;
}
          • 0
            @ 2025-12-7 9:21:45 
            #include<bits/stdc++.h>
#define lc(p) tr[p].ls
#define rc(p) tr[p].rs
using namespace std;
typedef long long ll;
int id,rt;
struct N{
	int ls,rs,v,rd,sz;
}tr[10000010];
mt19937 rd(999983);
int nd(int v){
	tr[++id]={0,0,v,rd(),1};
	return id;
}
void pushup(int p){
	tr[p].sz=tr[lc(p)].sz+tr[rc(p)].sz+1;
}
void split(int p,int v,int &x,int &y){
	if(!p){
		x=y=0;
		return ;
	}
	if(tr[p].v<=v){
		x=p;
		split(rc(p),v,rc(p),y);
	}
	else{
		y=p;
		split(lc(p),v,x,lc(p));
	}
	pushup(p);
}
int merge(int x,int y){
	if(!x||!y)return x+y;
	if(tr[x].rd<tr[y].rd){
		rc(x)=merge(rc(x),y);
		pushup(x);
		return x;
	} 
	else{
		lc(y)=merge(x,lc(y));
		pushup(y);
		return y;
	}
}
void ins(int v){
	int x,y,z;
	split(rt,v-1,x,y);
	split(y,v,z,y);
	rt=merge(merge(x,nd(v)),y);
}
void del(int v){
	int x,y,z;
	split(rt,v,x,y);
	split(x,v-1,x,z);
//	z=merge(lc(z),rc(z));
	rt=merge(x,y);
}
int getval(int p,int k){
	while(1){
		if(tr[lc(p)].sz+1==k)return tr[p].v;
		if(tr[lc(p)].sz>=k)p=lc(p);
		else k-=tr[lc(p)].sz+1,p=rc(p);
	}
}
int getrk(int v){
	int x,y;
	split(rt,v,x,y);
	int ans=tr[x].sz;
	rt=merge(x,y);
	return ans;
}
int getpre(int v){
	int x,y;
	split(rt,v,x,y);
	int ans=getval(x,tr[x].sz);
	rt=merge(x,y);
	return ans;
} 
int getnxt(int v){
	int x,y;
	split(rt,v-1,x,y);
	int ans=getval(y,1);
	rt=merge(x,y);
	return ans;
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n,q;
	cin>>n>>q;
	ins(-1);ins(1e9);
	for(int i=1,x;i<=n;i++){
		cin>>x;
		ins(x);
	}
	for(int i=1;i<=q;i++){
		int op,x;
		cin>>op>>x;
		if(op==0){
			ins(x);
		}
		else if(op==1){
			del(x);
		}
		else if(op==2){
			if(x>tr[rt].sz-2)cout<<"-1\n";
			else cout<<getval(rt,x+1)<<'\n';
		}
		else if(op==3){
			cout<<getrk(x)-1<<'\n';
		}
		else if(op==4){
			int ans=getpre(x);
			if(ans==-1)cout<<"-1\n";
			else cout<<ans<<'\n';
		}
		else if(op==5){
			int ans=getnxt(x);
			if(ans==1e9)cout<<"-1\n";
			else cout<<ans<<'\n';
		}
	}
	return 0;
}
            • 1

            *【pbds：tree】有序集合（Ordered Set）

            信息

            ID
            8118
            时间
            1000ms
            内存
            1024MiB
            难度
            9
            标签
            递交数
            249
            已通过
            18
            上传者
            1. Language
            2. 兼容模式
            3. 主题
            3. Worker 0, 19ms
            4. Powered by Hydro v5.0.1 Community