I.CF19D Points
树套树第一题。
思路1.线段树套线段树
因为内外的操作类似，很容易就能想到使用线段树套线段树，然后在线段树上二分来找到答案。
复杂度是\(O(n\log^2 n)\)，常数极大，因此被卡了。
代码：
#include<bits/stdc++.h>
using namespace std;
int n;
vector<pair<int,int> >vp;
struct opt{
int tp,x,y;
}q[200100];
struct Inner_SegTree{
vector<int>val,sum;
Inner_SegTree(){
val.clear(),sum.clear();
}
int size(){
return val.size();
}
void insert(int x){
val.push_back(x);
}
void construct(){
sort(val.begin(),val.end()),val.resize(unique(val.begin(),val.end())-val.begin());
sum.assign(val.size()<<2,0);
}
int ask(int x,int l,int r,int k){
if(val[r-1]<=k||!sum[x])return 0x3f3f3f3f;
if(r-l==1)return val[l];
register int mid=(l+r)>>1;
register int tmp=ask(x<<1|1,l,mid,k);
if(tmp!=0x3f3f3f3f)return tmp;
return ask(x+1<<1,mid,r,k);
}
void add(int x,int l,int r,int P,int k){
if(val[l]>P||val[r-1]<P)return;
sum[x]+=k;
if(r-l==1)return;
register int mid=(l+r)>>1;
add(x<<1|1,l,mid,P,k),add(x+1<<1,mid,r,P,k);
}
};
struct Outer_SegTree{
vector<int>val;
vector<Inner_SegTree>inn;
inline int size(){
return val.size();
}
inline void insert_outer(int x){
val.push_back(x);
}
inline void insert_inner(int x,int l,int r,int P,int Q){
if(val[l]>P||val[r-1]<P)return;
inn[x].insert(Q);
if(r-l==1)return;
int mid=(l+r)>>1;
insert_inner(x<<1|1,l,mid,P,Q),insert_inner(x+1<<1,mid,r,P,Q);
}
inline void construct_outer(){
sort(val.begin(),val.end()),val.resize(unique(val.begin(),val.end())-val.begin());
inn.resize(val.size()<<2);
}
inline void construct_inner(){
for(register auto x:vp)insert_inner(0,0,val.size(),x.first,x.second);
for(register auto &x:inn)x.construct();
}
inline void add(int x,int l,int r,int P,int Q,int k){
if(val[l]>P||val[r-1]<P)return;
inn[x].add(0,0,inn[x].size(),Q,k);
if(r-l==1)return;
register int mid=(l+r)>>1;
add(x<<1|1,l,mid,P,Q,k),add(x+1<<1,mid,r,P,Q,k);
}
inline pair<int,int> ask(int x,int l,int r,int P,int Q){
register int pmt=inn[x].ask(0,0,inn[x].size(),Q);
if(val[r-1]<=P||pmt==0x3f3f3f3f)return make_pair(0x3f3f3f3f,0x3f3f3f3f);
if(r-l==1)return make_pair(val[l],pmt);
register int mid=(l+r)>>1;
register pair<int,int> tmp=ask(x<<1|1,l,mid,P,Q);
if(tmp!=make_pair(0x3f3f3f3f,0x3f3f3f3f))return tmp;
return ask(x+1<<1,mid,r,P,Q);
}
inline void iterate(int x,int l,int r){
printf("%d:(%d,%d):",x,l,r);
for(register auto i:inn[x].val)printf("%d ",i);puts("");
if(r-l==1)return;
register int mid=(l+r)>>1;
iterate(x<<1|1,l,mid),iterate(x+1<<1,mid,r);
}
}seg;
inline void read(int &x){
x=0;
register char c=getchar();
while(c>'9'||c<'0')c=getchar();
while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar();
}
inline void print(int x){
if(x<=9)putchar('0'+x);
else print(x/10),putchar('0'+x%10);
}
int main(){
read(n);
for(register int i=1;i<=n;i++){
char s[10];
scanf("%s",s),read(q[i].x),read(q[i].y);
if(s[0]=='a')q[i].tp=1,vp.push_back(make_pair(q[i].x,q[i].y)),seg.insert_outer(q[i].x);
if(s[0]=='r')q[i].tp=2;
if(s[0]=='f')q[i].tp=3;
}
seg.construct_outer();
// for(auto x:seg.val)printf("%d ",x);puts("");
seg.construct_inner();
// seg.iterate(0,0,seg.size());
for(register int i=1;i<=n;i++){
if(q[i].tp==1)seg.add(0,0,seg.val.size(),q[i].x,q[i].y,1);
if(q[i].tp==2)seg.add(0,0,seg.val.size(),q[i].x,q[i].y,-1);
if(q[i].tp==3){
register pair<int,int> tmp=seg.ask(0,0,seg.val.size(),q[i].x,q[i].y);
if(tmp==make_pair(0x3f3f3f3f,0x3f3f3f3f))putchar('-'),putchar('1'),putchar('\n');
else print(tmp.first),putchar(' '),print(tmp.second),putchar('\n');
}
}
return 0;
}
思路2.线段树套set。
因为内层线段树里面要实现的操作一共只有插入、删除和求upper_bound，因此直接用std::set替代即可。
似乎线段树比set常数还要小？最终结果是set时间长一点，仍然TLE。
#include<bits/stdc++.h>
using namespace std;
int n;
vector<pair<int,int> >vp;
struct opt{
int tp,x,y;
}q[200100];
struct Inner_Set:set<int>{
int ask(int x){
set<int>::iterator it=upper_bound(x);
if(it==end())return 0x3f3f3f3f;
return *it;
}
};
struct Outer_SegTree{
vector<int>val;
vector<Inner_Set>inn;
inline int size(){
return val.size();
}
inline void insert_outer(int x){
val.push_back(x);
}
inline void construct_outer(){
sort(val.begin(),val.end()),val.resize(unique(val.begin(),val.end())-val.begin());
inn.resize(val.size()<<2);
}
inline void add(int x,int l,int r,int P,int Q,int k){
if(val[l]>P||val[r-1]<P)return;
if(k==1)inn[x].insert(Q);
else inn[x].erase(Q);
if(r-l==1)return;
register int mid=(l+r)>>1;
add(x<<1|1,l,mid,P,Q,k),add(x+1<<1,mid,r,P,Q,k);
}
inline pair<int,int> ask(int x,int l,int r,int P,int Q){
register int pmt=inn[x].ask(Q);
if(val[r-1]<=P||pmt==0x3f3f3f3f)return make_pair(0x3f3f3f3f,0x3f3f3f3f);
if(r-l==1)return make_pair(val[l],pmt);
register int mid=(l+r)>>1;
register pair<int,int> tmp=ask(x<<1|1,l,mid,P,Q);
if(tmp!=make_pair(0x3f3f3f3f,0x3f3f3f3f))return tmp;
return ask(x+1<<1,mid,r,P,Q);
}
}seg;
inline void read(int &x){
x=0;
register char c=getchar();
while(c>'9'||c<'0')c=getchar();
while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar();
}
inline void print(int x){
if(x<=9)putchar('0'+x);
else print(x/10),putchar('0'+x%10);
}
int main(){
read(n);
for(register int i=1;i<=n;i++){
char s[10];
scanf("%s",s),read(q[i].x),read(q[i].y);
if(s[0]=='a')q[i].tp=1,vp.push_back(make_pair(q[i].x,q[i].y)),seg.insert_outer(q[i].x);
if(s[0]=='r')q[i].tp=2;
if(s[0]=='f')q[i].tp=3;
}
seg.construct_outer();
for(register int i=1;i<=n;i++){
if(q[i].tp==1)seg.add(0,0,seg.val.size(),q[i].x,q[i].y,1);
if(q[i].tp==2)seg.add(0,0,seg.val.size(),q[i].x,q[i].y,-1);
if(q[i].tp==3){
register pair<int,int> tmp=seg.ask(0,0,seg.val.size(),q[i].x,q[i].y);
if(tmp==make_pair(0x3f3f3f3f,0x3f3f3f3f))putchar('-'),putchar('1'),putchar('\n');
else print(tmp.first),putchar(' '),print(tmp.second),putchar('\n');
}
}
return 0;
}
思路3.树状数组套set。
介于这题卡常卡的丧心病狂，考虑用常数更小的树状数组维护set。
思路就是用树状数组维护\(y\)坐标，支持单点的set插入/删除以及后缀\(\max\)（关于后缀的方法，实际上只需要把正常树状数组里面\(+\operatorname{lowbit}\)和\(-\operatorname{lowbit}\)的地方互换一下即可。
复杂度\(O(n\log^2n)\)。
代码：
#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
int n,val[200100],m;
set<pii>s[200100];
struct opt{
int tp,x,y;
}q[200100];
inline void read(int &x){
x=0;
register char c=getchar();
while(c>'9'||c<'0')c=getchar();
while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar();
}
inline void print(int x){
if(x<=9)putchar('0'+x);
else print(x/10),putchar('0'+x%10);
}
void ins(int x,pii k){
while(x)s[x].insert(k),x-=x&-x;
}
void del(int x,pii k){
while(x)s[x].erase(k),x-=x&-x;
}
pii ask(int x,pii k){
pii res=make_pair(0x3f3f3f3f,0x3f3f3f3f);
while(x<=m)res=min(res,*s[x].lower_bound(k)),x+=x&-x;
return res;
}
int main(){
read(n);
for(register int i=1;i<=n;i++){
char str[10];
scanf("%s",str),read(q[i].x),read(q[i].y);
if(str[0]=='a')q[i].tp=1;
if(str[0]=='r')q[i].tp=2;
if(str[0]=='f')q[i].tp=3,q[i].x++,q[i].y++;
val[++m]=q[i].y;
}
sort(val+1,val+m+1),m=unique(val+1,val+m+1)-val+1;
for(int i=1;i<=m;i++)s[i].insert(make_pair(0x3f3f3f3f,0x3f3f3f3f));
for(register int i=1;i<=n;i++){
if(q[i].tp==1)ins(lower_bound(val+1,val+m,q[i].y)-val,make_pair(q[i].x,q[i].y));
if(q[i].tp==2)del(lower_bound(val+1,val+m,q[i].y)-val,make_pair(q[i].x,q[i].y));
if(q[i].tp==3){
register pii tmp=ask(lower_bound(val+1,val+m,q[i].y)-val,make_pair(q[i].x,q[i].y));
if(tmp==make_pair(0x3f3f3f3f,0x3f3f3f3f))putchar('-'),putchar('1'),putchar('\n');
else print(tmp.first),putchar(' '),print(tmp.second),putchar('\n');
}
}
return 0;
}