UOJ Logo

NOI.AC

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#205257#3670. BZxc2006111005927ms150688kbC++115.0kb2024-06-30 10:38:412024-06-30 13:15:04

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
*/

Details

小提示:点击横条可展开更详细的信息

Subtask #1:

score: 20
Accepted

Test #1:

score: 20
Accepted
time: 45ms
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: 68ms
memory: 105152kb

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: 49ms
memory: 105176kb

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: 676ms
memory: 139728kb

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: 919ms
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: 626ms
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: 1211ms
memory: 149880kb

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: 748ms
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: 1585ms
memory: 150076kb

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