题目描述

同CCY

思路

哈希，set操作

CCY提供的check函数~（因为我懒）~

tuple<>Wiki

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
int n, m, ki, u, v, x, y, li, pi, qi, t;
struct Node {
	long long cnt;
	int ct;
	bool operator<(const Node& b) const {
		if (cnt != b.cnt) {
			return cnt > b.cnt;
		}
		return ct < b.ct;
	}
};
map<pair<int,int>, long long> adj;
set<Node> st[N];
vector<tuple<int, int, long long> > eve[N];
vector<int> q;
int no_out, city_dui;
bool has_out[N], add_dui[N];
inline void check(int u,int l_id) {
	if(!has_out[u]&&!st[u].empty()) {
		has_out[u]=1;
		no_out--;
	}
	if(has_out[u]&&(st[u].empty())) {
		has_out[u]=0;
		no_out++;
	}
	if(st[l_id].begin()->ct==u&&st[u].begin()->ct!=l_id) {
		city_dui--;
		add_dui[u]=0;
		add_dui[l_id]=0;
	}
	if(st[st[u].begin()->ct].begin()->ct==u&&!add_dui[st[u].begin()->ct]) {
		city_dui++;
		add_dui[u]=1;
		add_dui[st[u].begin()->ct]=1;
	}
}
inline void update(int& a, int& b, long long& oldc, long long& newc) {
	int l_id = st[a].size() ? st[a].begin()->ct : 0;
	if (oldc != 0) {
		st[a].erase({oldc, b});
	}
	if (newc != 0) {
		adj[ {a,b}] = newc;
		st[a].insert({newc, b});
	} else {
		adj[ {a,b}]=0;
	}
	check(a, l_id);
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr), cout.tie(nullptr);
	cin >> n >> m;
	no_out = n;
	for(t = 1; t <= m; t++) {
		cin >> ki;
		if(t==41) {
			t++;
			t--;
		}
		for(int i = 0; i < ki; i++) {
			cin >> u >> v >> x >> y;
			long long old_u = adj[ {u,v}];
			long long old_v = adj[ {v,u}];
			long long new_u = old_u + x;
			long long new_v = old_v + x;
			update(u, v, old_u, new_u);
			update(v, u, old_v, new_v);
			if(t + y <= m) {
				eve[t + y].push_back( tuple<int, int, long long>(  u, v, (long long)(-x) ) );
			}
		}
		for (auto& e : eve[t]) {
			int u = get<0>(e);
			int v = get<1>(e);
			long long del = get<2>(e);
			long long old_u = adj[ {u,v}];
			long long old_v = adj[ {v,u}];
			long long new_u = old_u + del;
			long long new_v = old_v + del;
			update(u, v, old_u, new_u);
			update(v, u, old_v, new_v);
		}
		cin >> li;
		q.resize(li);
		for(int i = 0; i < li; i++) {
			cin >> q[i];
			cout << (st[q[i]].empty() ? 0 : st[q[i]].begin()->ct) << '\n';
		}
		cin >> pi >> qi;
		if (pi == 1) {
			cout << no_out << '\n';
		}
		if (qi == 1) {
			cout << city_dui << '\n';
		}
	}
	return 0;
}

题目描述

扶苏是洛谷王国的航空局长，她掌管着洛谷境内一切民航飞机的航线安排。

洛谷王国共有$n$座城市，从$1$至$n$编号。任意两座城市之间都有一条双向航线。但不一定每条航线都有航班经过。

初始时，每条航线上都没有航班。在接下来$m$天里，扶苏会根据对人们出行需求的预测，在若干天内向一些航线上添加航班，并做出一些查询。

每次添加航班的格式是：$u$ $v$ $x$ $y$，表示在城市$u$和城市$v$的航线上添加$x$个航班，这条命令会在$y$天后取消。即给从增加命令下达当天到下达后第$y−1$天这$y$天里$u$到$v$的航线添加$x$个航班。在第$y$天不再添加$x$个航班。可能会有多个命令影响同一天的航班数，这些命令可以叠加生效。

对于一个城市$u$，称$u$的“主要出行目的地”是当前时刻与$u$之间的航线上航班数最多的城市（如果存在多个这样的城市，取编号最小的）；特别的，如果u与任何城市之间的航线上航班数均为$0$，称$u$是一个“封闭城市”，且它没有“主要出行目的地”；如果两座城市互为 “主要出行目的地”，称他们是“交流城市对**”。

每天开始时，扶苏会先下达若干条添加航班的命令。在处理完这些命令后，你会收到若干个查询某个城市的“主要出行目的地”的请求。此外，你还.可.能希望求出此时的“封闭城市”和“交流城市对”各有多少。

请你帮助处理扶苏下达的添加航班的指令，并回答她的询问

输入格式

第一行是两个整数，依次表示城市数量$n$和天数$m$。

接下来$3m$行，每三行一组描述一天中的事件，格式如下：

• 第一行：首先是一个整数$k_i$，表示当天下达添加航班的命令数。接下来有$4k_i$个整数，依次表示这$k_i$条命令。格式见【题目描述】。

• 第二行：首先是一个整数 $l_i$，表示当天查询“主要出行目的地”的数量。接下来 $l_i$ 个整数，依次表示每次查询的对象。

• 第三行：只有两个整数 $p_i$,$q_i$，取值均为$0$或$1$。分别表示当天是否需要查询“封闭城市”和“交流城市对”的数量。如果 $p_i=1$，表示查询”封闭城市“的数量，如果 $p_i=0$，表示不需要查询；qi的含义同理

输入样例

3 3
2 1 2 2 3 1 3 3 2
1 1
0 0
1 2 3 3 1
2 1 2
0 1
0
2 1 3
1 1

输出样例

3
3
3
1
2
0
1
1

数据范围

以下为题解

思路

首先对于每个城市，它的 主要出行目的地 即为到其他城市的航线中航班最多的那一个。

考虑使用线段树来维护。

显然，用朴素的线段树无论空间或是时间都不能满足.但由于 $k_i$ 和 $l_i$ 的总和最大只到 $2e5$ 我们可以使用动态开点线段树来进行维护。

对于第 $i$ 天的每组 $u,v,x,y$ 在第 $i$ 天增加 $x$ 并在第 $i+y$ 天减去 $x$,维护 $1 \sim n$ 城市的最大值。

因为我们查询的总是 $1 \sim n$ 中的最大值，所以区间查询的值就是根节点的值

接着是维护 封闭城市 这一项。

一个城市为封闭城市，当且仅当它所有航线的航班均为零。

我们可以在每次修改后查询最大值并维护。

交流城市对 这一项会变化有两种情况：

1. 原来不是城市对的，现在变为了城市对
2. 原来是城市对的，现在不再是城市对

我们可以在每次修改后查询最大值的城市编号并维护。

时间复杂度 $O(\sum_{i=1}^{m}{k_i}\log n)$

代码

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
struct node{
	int data,id,l,r,ls=-1,rs=-1;
}tr[N*2*18];
int n,m,idx;
struct oper{
	int u,v,x;
}; 
vector<oper> op[N]; 
void push_up(int u)
{
	int maxn,id;
	if(tr[u].ls!=-1&&tr[u].rs==-1)
		maxn=tr[tr[u].ls].data,id=tr[tr[u].ls].id;
	else if(tr[u].ls==-1&&tr[u].rs!=-1)
		maxn=tr[tr[u].rs].data,id=tr[tr[u].rs].id;
	else if(tr[tr[u].ls].data>=tr[tr[u].rs].data)
		maxn=tr[tr[u].ls].data,id=tr[tr[u].ls].id;
	else
		maxn=tr[tr[u].rs].data,id=tr[tr[u].rs].id;
	tr[u].data=maxn,tr[u].id=id;
}
void modify(int u,int x,int k)//单点修改+动态开点
{
	if(tr[u].l==x&&tr[u].r==x)
	{
		tr[u].id=tr[u].l;
		tr[u].data+=k;
		if(tr[u].data==0)
			tr[u].id=0;
		return;
	}
	int mid=(tr[u].l+tr[u].r)>>1;
	if(x<=mid)
	{
		if(tr[u].ls==-1)
		{
			tr[u].ls=++idx;
			tr[idx].l=tr[u].l;
			tr[idx].r=mid;
		}
		modify(tr[u].ls,x,k);
	}else
	{
		if(tr[u].rs==-1)
		{
			tr[u].rs=++idx;
			tr[idx].l=mid+1;
			tr[idx].r=tr[u].r;
		}
		modify(tr[u].rs,x,k);
	}
	push_up(u); 
}
int no_out,city_dui;
bool has_out[N],add_dui[N];
void check(int u,int l_id)
{
  //维护封闭城市
	if(!has_out[u]&&tr[u].data)
	{
		has_out[u]=1;
		no_out--;
	}
	if(has_out[u]&&(!tr[u].data))
	{
		has_out[u]=0;
		no_out++;
	}
  //维护交流城市对
	if(tr[l_id].id==u&&tr[u].id!=l_id)
	{
		city_dui--;
		add_dui[u]=0;
		add_dui[l_id]=0;
	}
	if(tr[tr[u].id].id==u&&!add_dui[tr[u].id])	
	{
		city_dui++;
		add_dui[u]=1;
		add_dui[tr[u].id]=1;
	}
	
} 
int main()
{
	scanf("%d%d",&n,&m);
	no_out=n,city_dui=0;
	for(int i=1;i<=n;i++)
	{
    //初始化n个根节点
		tr[++idx].data=0;
		tr[idx].l=1;
		tr[idx].ls=-1;
		tr[idx].r=n;
		tr[idx].rs=-1;
	}
	for(int i=1;i<=m;i++)
	{
		int k;
		scanf("%d",&k);
		while(k--)
		{
			int u,v,x,y;
			scanf("%d%d%d%d",&u,&v,&x,&y);
			if(i+y<=m) //在第i+y天减掉
				op[i+y].push_back({u,v,x});
			int l_id=tr[u].id;
			modify(u,v,x);
			check(u,l_id);
			l_id=tr[v].id;
			modify(v,u,x);
			check(v,l_id);
		}
		int vs=op[i].size();
		if(vs!=0)
		{
			for(int k=vs-1;k>=0;k--)
			{
				int l_id=tr[op[i][k].u].id;
				modify(op[i][k].u,op[i][k].v,-op[i][k].x);
				check(op[i][k].u,l_id);
				l_id=tr[op[i][k].v].id;
				modify(op[i][k].v,op[i][k].u,-op[i][k].x);
				check(op[i][k].v,l_id);
				op[i].pop_back();
			}
		}
    // O(1)查询
		int l;
		scanf("%d",&l);
		while(l--)
		{
			int x;
			scanf("%d",&x);
			printf("%d\n",tr[x].id);
		}
		int p,q;
		scanf("%d%d",&p,&q);
		if(p)
			printf("%d\n",no_out);
		if(q)
			printf("%d\n",city_dui); 
	}
	return 0;
}