tokitsukaze > 2018牛客网暑期ACM多校训练营（第六场）I.Team Rocket(STL)

2018牛客网暑期ACM多校训练营（第六场）I.Team Rocket(STL)

2018-08-04

STL

转载请注明出处：http://tokitsukaze.live/

题目链接：https://www.nowcoder.com/acm/contest/144/I

题意：
给n个列车和m个爆破点。每个列车有一个运行区间[L,R]。刚开始，所有列车都在运行。每次爆破一个点后输出有多少运行中的列车因为这次爆破而停止运行。然后那些列车就停止运行了。
最后输出每个列车是因为第几次爆破而停止运行的。
爆破点是加密的，所以强制在线。

题解：
先把L从小到大离散化一下，然后开2e5个set存每个R和列车的id，注意R是要求从大到小存。
然后每次爆破，暴力遍历每个set，遇到满足的就记录，并从set里删除，遇到第一个不满足的就break。
但是这样每次可能会遍历2e5次。所以用一个双向链表维护，遍历的时候跳掉那些size等于0的set。

*赛后想了想，这种做法还是能被卡成n^2，所以仅供参考…

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
#include <bits/stdc++.h>
using namespace std;
#pragma comment(linker, "/STACK:1024000000,1024000000")
#define mem(a,b) memset((a),(b),sizeof(a))
#define MP make_pair
#define pb push_back
#define fi first
#define se second
#define sz(x) (int)x.size()
#define all(x) x.begin(),x.end()
using namespace __gnu_cxx;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> PII;
typedef pair<ll,ll> PLL;
typedef vector<int> VI;
typedef vector<ll> VL;
void go();
int main(){
	#ifdef tokitsukaze
		freopen("TEST.txt","r",stdin);
	#endif
	go();return 0;
}
const int INF=0x3f3f3f3f;
const ll LLINF=0x3f3f3f3f3f3f3f3f;
const double PI=acos(-1.0);
const double eps=1e-6;
const int MAX=2e5+10;
const ll mod=998244353;
/*********************************  head  *********************************/
struct node
{
	int fi,se;
	node(){}
	node(int l,int r) :fi(l),se(r){}
	friend bool operator<(node a,node b)
	{
		if(a.fi==b.fi) return a.se<b.se;
		return a.fi>b.fi;
	}
	friend bool operator!=(node a,node b)
	{
		return a.fi!=b.fi||a.se!=b.se;
	}
};
set<node> mp[MAX];
PII a[MAX];
int res[MAX],nex[MAX],p[MAX];
void go()
{
	int t,n,m,i,ans,x,tot,time,cas=1;
	node tmp;
	ll pre,now;
	read(t);
	while(t--)
	{
		unordered_map<int,int> id;
		VI xx;
		read(n,m);
		for(i=1;i<=n;i++)
		{
			read(a[i].fi,a[i].se);
			xx.pb(a[i].fi);
			res[i]=0;
			nex[i]=i+1;
			p[i]=i-1;
		}
		sort(all(xx));
		xx.resize(unique(all(xx))-xx.begin());
		for(i=0;i<sz(xx);i++) id[xx[i]]=i+1;
		tot=sz(xx);
		for(i=1;i<=tot;i++) mp[i].clear();
		for(i=1;i<=n;i++) mp[id[a[i].fi]].insert(node(a[i].se,i));
		pre=0;
		printf("Case #%d:\n",cas++);
		for(time=1;time<=m;time++)
		{
			read(x);
			x=(x^pre);
			ans=0;
			now=1;
			for(i=1;i<=tot;i=nex[i])
			{
				if(xx[i-1]>x) break;
				tmp=node(-INF,-INF);
				for(auto &it:mp[i])
				{
					if(tmp!=node(-INF,-INF)) mp[i].erase(tmp);
					if(it.fi<x) break;
					ans++;
					res[it.se]=time;
					now=now*it.se%mod;
					tmp=it;
				}
				if(tmp!=node(-INF,-INF)) mp[i].erase(tmp);
				if(sz(mp[i])==0)
				{
					nex[p[i]]=nex[i];
					p[nex[i]]=p[i];
				}
			}
			if(now==1&&res[1]!=time) now=0;
			pre=now;
			printf("%d\n",ans);
		}
		for(i=1;i<=n;i++) printf("%d%c",res[i]," \n"[i==n]);
	}
}