[树套树]K大数查询

阅读原文时间：2023年07月16日阅读：2

有N个位置，M个操作。操作有两种，每次操作如果是1 a b c的形式表示在第a个位置到第b个位置，每个位置加入一个数c
如果是2 a b c形式，表示询问从第a个位置到第b个位置，第C大的数是多少。
为了强制在线，每一次的a，b是加密的，需要异或lastans的后8位进行解密，其中lastans为上次输出的结果，初始为零。
如果解密后a>b则先交换a,b
数据保证解密后a,b不会超过N
如果解密后a，b出现0，则赋值为1。

来历：bzoj上的一道题，经过子祯学长的魔改后，数据范围变得很奇怪…

算法：树套树；

权值线段树套线段树；

套线段树有技巧：一颗线段树可以先只创造一个点，其他需要的节点需要用到的时候再开就可以了；

其他的也没什么可说了，看代码吧：

（不要交到bzoj上，过不了，这是经过魔改的题目）

（不建议借鉴，初次写这种题，code还比较稚嫩）

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
#define FILE "dealing"
#define up(i,j,n) for(int i=(j);i<=(n);i++) #define pii pair
#define LL long long
#define mem(f,g) memset(f,g,sizeof(f))
namespace IO{
char buf[1<<15],*fs,*ft; int gc(){return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),fs==ft))?-1:*fs++;} int read(){ int ch=gc(),f=0,x=0; while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=gc();}
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=gc();} return f?-x:x; } int readint(){ int ch=getchar(),f=0,x=0; while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();} return f?-x:x; } }using namespace IO; const int maxn=201000,inf=1000000000; int n,m; int ch[maxn],l[maxn],r[maxn],k[maxn],f[maxn]; struct node{ int k,id; bool operator<(const node& b)const{return k>1)
const int maxm=20000000;
int root=0,c[maxn][2],id[maxn],cnt=0;//权值线段树
LL sum[maxm],flag[maxm];
int d[maxm][2],len=0;//区间线段树
int x,y,key;
void pushdown(int o,int l,int r){
if(flag[o]){
if(l!=r&&!d[o][0])d[o][0]=++len;
if(l!=r&&!d[o][1])d[o][1]=++len;
sum[d[o][0]]+=flag[o]*(mid-l+1);
sum[d[o][1]]+=flag[o]*(r-mid);
flag[d[o][0]]+=flag[o];
flag[d[o][1]]+=flag[o];
flag[o]=0;
}
}
void change(int l,int r,int& o){
if(l>y||r=x&&r<=y){ sum[o]+=r-l+1; flag[o]++; return; } pushdown(o,l,r); change(l,mid,d[o][0]); change(mid+1,r,d[o][1]); sum[o]=sum[d[o][1]]+sum[d[o][0]]; } void insert(int l,int r,int& o){ if(l>key||ry||r=x&&r<=y)return sum[o]; pushdown(o,l,r); return query2(l,mid,d[o][0])+query2(mid+1,r,d[o][1]); } int query1(int l,int r,int o){ if(!o||r<=key)return 0; if(l>key)return query2(1,n,id[o]);
return query1(l,mid,c[o][0])+query1(mid+1,r,c[o][1]);
}
int Query(int l,int r,int val){
x=l,y=r,key=val;
return query1(1,L,root)+1;
}
int Q(int l,int r,int k){
int left=1,right=L,midd,p;
while(left+1>1;
if(Query(l,r,midd)>k)left=midd;
else right=midd;
}
if(Query(l,r,left)>k&&Query(l,r,right)<=k)return right; else return left; } }using namespace OI; void print(int *a,int n){up(i,1,n)printf("%d ",a[i]);cout<r[i])swap(l[i],r[i]);
if(ch[i]==1)init(l[i],r[i],f[i]);
if(ch[i]==2)printf("%d\n",pre=Cnt[Q(l[i],r[i],k[i])].k);
}
return 0;
}

手机扫一扫

移动阅读更方便

你可能感兴趣的文章

LYK loves music

Go，从命名开始！Go的关键字和标识符全列表手册和代码示例！

为何每个开发者都在谈论Go？

Go 并发编程 - Goroutine 基础（一）

【Netty】03-进阶

从零实现俄罗斯方块（c语言+思路分析）