ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#205256 | #3670. B | Zxc200611 | 100 | 5204ms | 150688kb | C++11 | 5.0kb | 2024-06-30 10:30:47 | 2024-06-30 13:14:50 |
answer
/*
每行每列有个 tag。维护这个 tag 序列。查询 (x,y) 时,找到坐标 x 行上、坐标 y 列上的 tag。
如果这两个 tag 都是一开始就有的,那么只需要求出现在坐标 <x、<y 的新增行列分别有多少即可。
否则设行的 tag 较晚出现。那么需要知道这行被添加直到现在,现在坐标 <=y 的新增列有多少。
如果用平衡树维护插入的列,需要支持插入数、询问区间中值 <y 的数有多少个。
或许可以替罪羊树套 set?
替罪羊树重构大小之和貌似不带 log。那么 2log?
*/
#include<bits/stdc++.h>
#include<bits/extc++.h>
using namespace std;
using pset=__gnu_pbds::tree<int,__gnu_pbds::null_type,less<int>,__gnu_pbds::rb_tree_tag,__gnu_pbds::tree_order_statistics_node_update>;
struct ScapeGoatTree
{
static constexpr double alpha=0.75;
struct Node
{
int ls,rs;
int x,y,adx;
pset sty;
void addX(int _adx)
{
x+=_adx;
adx+=_adx;
}
};
Node t[510000];
int ncnt,rt;
queue<int> rec;
void print()
{
cout<<"-------------------------------------------------------------------------"<<endl;
cout<<"rt="<<rt<<endl;
for(int i=0;i<=ncnt;i++)
printf("Node #%d: ls=%d rs=%d x=%d y=%d adx=%d\n",i,t[i].ls,t[i].rs,t[i].x,t[i].y,t[i].adx);
cout<<"-------------------------------------------------------------------------"<<endl;
}
int newNode()
{
if(rec.empty())
return ++ncnt;
int x=rec.front();
rec.pop();
return x;
}
void recycle(int u)
{
t[u]=(Node){0,0,0,0,0,pset()};
rec.push(u);
}
void pushDown(int u)
{
if(t[u].adx)
{
if(t[u].ls) t[t[u].ls].addX(t[u].adx);
if(t[u].rs) t[t[u].rs].addX(t[u].adx);
t[u].adx=0;
}
}
void getAll(int u,vector<pair<int,int>> &p)
{
pushDown(u);
if(t[u].ls) getAll(t[u].ls,p);
p.emplace_back(t[u].x,t[u].y);
if(t[u].rs) getAll(t[u].rs,p);
recycle(u);
}
int build(vector<pair<int,int>> &p,int l,int r)
{
if(l>r)
return 0;
int mid=(l+r)>>1,u=newNode();
t[u].x=p[mid].first,t[u].y=p[mid].second;
for(int i=l;i<=r;i++)
t[u].sty.insert(p[i].second);
t[u].ls=build(p,l,mid-1);
t[u].rs=build(p,mid+1,r);
return u;
}
void addX(int u,int xl,int adx)
{
if(!u)
return;
pushDown(u);
if(t[u].x>=xl)
{
t[u].x+=adx,t[t[u].rs].addX(adx);
addX(t[u].ls,xl,adx);
}
else
addX(t[u].rs,xl,adx);
}
int insert(int u,int x,int y)
{
if(!u)
{
u=newNode();
t[u].x=x,t[u].y=y;
t[u].sty.insert(y);
return u;
}
t[u].sty.insert(y);
pushDown(u);
if(x<=t[u].x) t[u].ls=insert(t[u].ls,x,y);
else t[u].rs=insert(t[u].rs,x,y);
return u;
}
int checkRebuild(int u,int x)
{
if(!u)
return 0;
if(max<int>(t[t[u].ls].sty.size(),t[t[u].rs].sty.size())>t[u].sty.size()*alpha)
{
// cout<<"Rebuild"<<endl;
vector<pair<int,int>> p;
getAll(u,p);
return build(p,0,p.size()-1);
}
pushDown(u);
if(x<=t[u].x) t[u].ls=checkRebuild(t[u].ls,x);
else t[u].rs=checkRebuild(t[u].rs,x);
return u;
}
void insert(int x,int y)
{
rt=insert(rt,x,y);
rt=checkRebuild(rt,x);
}
int findY(int u,int x)
{
if(!u)
return 0;
if(t[u].x==x)
return t[u].y;
pushDown(u);
if(t[u].x>=x) return findY(t[u].ls,x);
else return findY(t[u].rs,x);
}
int countLeX(int u,int xr)
{
if(!u)
return 0;
pushDown(u);
if(t[u].x<=xr) return countLeX(t[u].rs,xr)+1+t[t[u].ls].sty.size();
else return countLeX(t[u].ls,xr);
}
int countLeXGeY(int u,int xr,int yr)
{
if(!u)
return 0;
pushDown(u);
if(t[u].x<=xr)
{
return countLeXGeY(t[u].rs,xr,yr)
+(t[u].x<=xr&&t[u].y>=yr)
+t[t[u].ls].sty.size()-t[t[u].ls].sty.order_of_key(yr);
}
else
return countLeXGeY(t[u].ls,xr,yr);
}
};
int q;
ScapeGoatTree sgt[2]; // row col
int resx=0,resy=0;
void query(int x,int y)
{
// cout<<"Query x="<<x<<" y="<<y<<endl;
int tr=sgt[0].findY(sgt[0].rt,x),tc=sgt[1].findY(sgt[1].rt,y);
// cout<<"tr="<<tr<<" tc="<<tc<<endl;
if(tr==0&&tc==0)
{
resx=x-sgt[0].countLeX(sgt[0].rt,x);
resy=y-sgt[1].countLeX(sgt[1].rt,y);
return;
}
if(tr>tc)
{
resx=tr;
resy=y-sgt[1].countLeXGeY(sgt[1].rt,y,tr);
return;
}
if(tc>tr)
{
resy=tc;
resx=x-sgt[0].countLeXGeY(sgt[0].rt,x,tc);
return;
}
assert(0);
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cin>>q;
for(int i=1;i<=q;i++)
{
int ty,x,y;
cin>>ty;
if(ty<=2)
{
cin>>x;
x=x+resx+resy;
// cout<<"AddX typ="<<2-ty<<" pos="<<x<<endl;
sgt[2-ty].addX(sgt[2-ty].rt,x,1);
// cout<<"Insert typ="<<2-ty<<" pos="<<x<<" tme="<<i<<endl;
sgt[2-ty].insert(x,i);
// sgt[2-ty].print();
}
if(ty==3)
{
cin>>x>>y;
x=x+resx+resy,y=y+resx-resy;
query(x,y);
cout<<resx<<" "<<resy<<'\n';
}
}
}
/*
15
2 53
1 -76
1 2
3 -40 77
3 -98 33
2 234
1 93
1 223
1 48
2 161
3 160 10
2 11
2 10
2 -11
3 -107 -63
-40 75
-63 -82
15 25
-67 -75
*/
详细
小提示:点击横条可展开更详细的信息
Subtask #1:
score: 20
Accepted
Test #1:
score: 20
Accepted
time: 55ms
memory: 105156kb
input:
1000 2 10 1 -10 1 -9 1 -1 2 -1 1 7 2 -7 2 0 1 -6 2 -1 2 5 2 8 2 -1 2 -10 1 -5 2 -7 1 -1 1 5 2 10 3 -...
output:
-5 0 11 -4 22 0 5 0 -10 -4 -1 27 -10 -7 -6 9 -1 -3 14 0 41 4 14 -6 47 8 -1 37 -4 50 -8 46 -4 46 66 -...
result:
ok 335 lines
Test #2:
score: 0
Accepted
time: 40ms
memory: 105144kb
input:
1000 2 53 1 -76 1 2 3 -40 77 3 -98 33 2 234 1 93 1 223 1 48 2 161 3 160 10 2 11 2 10 2 -11 3 -107 -6...
output:
-40 75 -63 -82 15 25 -67 -75 -9 -26 17 -80 -52 37 13 -34 80 -15 -60 30 -7 22 -84 33 -80 49 -77 -45 4...
result:
ok 348 lines
Test #3:
score: 0
Accepted
time: 32ms
memory: 105172kb
input:
1000 3 10 -27 1 -5 3 63 -58 1 9 1 -26 1 4 3 -44 -48 1 -6 2 -31 2 22 1 17 1 23 2 -26 3 -38 65 2 -20 1...
output:
10 -27 46 -22 -20 18 -40 22 -23 -13 -27 -38 27 -50 27 18 -50 -3 -14 -35 -25 -39 32 -43 -32 -39 -1 18...
result:
ok 339 lines
Subtask #2:
score: 25
Accepted
Test #4:
score: 25
Accepted
time: 628ms
memory: 139724kb
input:
100000 1 -9454 3 -4285 5319 1 -6044 3 2706 8704 3 5236 -10626 3 -7831 -15865 1 15317 1 7247 1 1587 3...
output:
-4285 5318 3739 -901 8074 -5987 -5744 -1806 -6705 8510 9757 -2850 -9264 9405 -3476 9639 8720 -767 58...
result:
ok 50132 lines
Test #5:
score: 0
Accepted
time: 894ms
memory: 139804kb
input:
100000 1 323 1 -288 3 -696 916 3 455 1182 1 558 1 566 3 -275 -901 1 -801 3 727 186 1 -353 3 -1629 -1...
output:
-696 914 673 -428 -30 199 896 -45 -778 -416 773 897 -250 552 -867 -946 653 66 335 -617 635 -706 54 -...
result:
ok 50076 lines
Test #6:
score: 0
Accepted
time: 549ms
memory: 140960kb
input:
100000 3 -7570 87252 1 714 3 -61731 174072 1 -69600 1 -111704 1 -52550 3 -55466 46814 1 -65991 3 351...
output:
-7570 87252 17951 79250 41735 -14486 62417 87714 92447 33993 -55929 46559 -63298 85147 88670 817 259...
result:
ok 50105 lines
Subtask #3:
score: 50
Accepted
Test #7:
score: 50
Accepted
time: 908ms
memory: 149884kb
input:
100000 3 7716 -3461 3 5353 -17984 1 1188 3 1953 -24674 3 5268 -10824 2 -2474 1 1742 2 -13160 1 -6369...
output:
7716 -3461 9608 -6807 4754 -8259 1763 2189 -9898 1106 -1087 819 9177 20 -3108 -5939 7315 -3708 5229 ...
result:
ok 33069 lines
Test #8:
score: 0
Accepted
time: 767ms
memory: 150688kb
input:
100000 3 1505 -51200 2 137894 2 65975 3 -36771 -33998 2 114039 2 19486 2 -19998 2 37350 1 25532 1 66...
output:
1505 -51200 -86466 18707 -30797 -26232 53384 -50300 8974 18671 -72752 31595 54708 -78771 66570 -6152...
result:
ok 33043 lines
Test #9:
score: 0
Accepted
time: 1331ms
memory: 150080kb
input:
100000 3 182 449 1 -1412 3 -454 -542 2 713 3 364 -732 1 -48 1 578 3 159 -22 3 202 63 2 366 2 333 3 -...
output:
182 449 177 -809 -268 253 143 -544 -199 747 -685 90 265 825 -606 -636 -5 -242 202 -390 829 615 -652 ...
result:
ok 33223 lines
Extra Test:
score: 0
Extra Test Passed