寒亭网站建设,域名个人备案查询,wordpress是单线程,网络推广网络营销公司传送门 文章目录目录#xff1a;题意#xff1a;思路#xff1a;目录#xff1a;
题意#xff1a;
你有nnn头奶牛#xff0c;mmm中不同种类的麦片#xff0c;每个麦片只有一箱#xff0c;给你每个奶牛第一和第二喜欢的麦片#xff0c;奶牛会先看第一喜欢的是否有题意思路目录
题意
你有nnn头奶牛mmm中不同种类的麦片每个麦片只有一箱给你每个奶牛第一和第二喜欢的麦片奶牛会先看第一喜欢的是否有有的话直接拿走否则看第二喜欢的是否有有的话直接拿走否则一箱不拿。
现在问题是奶牛排队领取对于每个0≤i≤N−10\le i\le N-10≤i≤N−1求如果从队伍前面移除前iii头奶牛有多少奶牛会取走一箱麦片。
1≤n,m≤1e51\le n,m\le 1e51≤n,m≤1e5
思路
第一反应是倒着考虑考虑每加入一个奶牛会产生什么影响
如果加入的奶牛第一喜好没有被之前的选择那么直接选择即可。如果加入奶牛的第一喜好被之前选择了那么由于其排在前面一定可以跟那个奶牛抢过来所以递归处理前面的奶牛即可。
由于一个奶牛最多会被修改三次复杂度得以保证O(n)O(n)O(n)。
#includebits/stdc.h
#define X first
#define Y second
#define L (u1)
#define R (u1|1)
#define Mid (tr[u].ltr[u].r1)
#define pb push_back
using namespace std;const int N1000010,INF0x3f3f3f3f,mod1e97;
typedef long long LL;int n,m;
int id[N],cnt;
int ans[N];
struct Node {int x,y;
}a[N];void dfs(int now) {if(now-1) return;int xa[now].x,ya[now].y;if(id[x]-1||id[x]now) {dfs(id[x]);id[x]now;} else if(id[y]-1||id[y]now) {dfs(id[y]);id[y]now;} else cnt--;
}void solve() {scanf(%d%d,n,m);for(int i1;in;i) {int x,y; scanf(%d%d,x,y);a[i]{x,y};}memset(id,-1,sizeof(id));for(int in;i1;i--) {cnt;int xa[i].x;if(id[x]!-1) dfs(i);else id[x]i;ans[i]cnt;}for(int i1;in;i) printf(%d\n,ans[i]);
}int main() {int _1;while(_--) {solve();}return 0;
}
