Contest Start

There are nn people participating in some contest, they start participating in xx minutes intervals. That means the first participant starts at time 0, the second participant starts at time x, the third — at time 2⋅x, and so on.

Duration of contest is tt minutes for each participant, so the first participant finishes the contest at time tt, the second — at time t+xt+x, and so on. When a participant finishes the contest, their dissatisfaction equals to the number of participants that started the contest (or starting it now), but haven't yet finished it.

Determine the sum of dissatisfaction of all participants.

Input

The first line contains a single integer kk (1≤k≤1000) — the number of test cases.

Each of the next kk lines contains three integers n, x, t (1≤n,x,t≤2⋅10^9) — the number of participants, the start interval and the contest duration.

Output

Print k lines, in the i-th line print the total dissatisfaction of participants in the ii-th test case.

题目理解：有n位选手，每隔x时间一位选手开始比赛，每位选手限定在t时间长度内完成比赛；

求每个t时间长度内，有多少选手正在比赛；

解题思路：1.在区间选手数恒定情况下人数为 t/x

                2.当到达后期只有n个选手不足以放到前面的区间时，会按区间递减直到0即最后一个选手开始比赛到结束比赛期间，没有更多的选手正在比赛了，

#include <iostream>using namespace std;int main()
{int t;cin>>t;while(t -- ){long long n, x,t, dis = 0;cin>>n>>x>>t;if(x > t){cout<<0<<endl;continue;}long long  c = t/x;//稳定的区间内的选手数量int a = n - c;//这样的稳定区间有几个，由于后面递减到零，那么相应的从0开始递增到t/x 需要 t/x个区间，因此稳定区间应当有 n - t/x；if(c < n)//当稳定区间人数小于总选手数时{dis += c*a;//先加上稳定区间数*稳定区间的选手数dis += (c-1+0)*c/2;//加上递减区间的选手数之和}else dis += (n-1)*n/2;//直接开始递减cout<<dis<<endl;}return 0;
}

---

---

B. Web of Lies

There are nn nobles, numbered from 11 to nn. Noble ii has a power of ii. There are also mm "friendships". A friendship between nobles aa and bb is always mutual.

A noble is defined to be vulnerable if both of the following conditions are satisfied:

• the noble has at least one friend, and
• all of that noble's friends have a higher power.

You will have to process the following three types of queries.

1. Add a friendship between nobles uu and vv.
2. Remove a friendship between nobles uu and vv.
3. Calculate the answer to the following process.

The process: all vulnerable nobles are simultaneously killed, and all their friendships end. Then, it is possible that new nobles become vulnerable. The process repeats itself until no nobles are vulnerable. It can be proven that the process will end in finite time. After the process is complete, you need to calculate the number of remaining nobles.

Note that the results of the process are not carried over between queries, that is, every process starts with all nobles being alive!

Input

The first line contains the integers nn and mm (1≤n≤2⋅1051≤n≤2⋅105, 0≤m≤2⋅1050≤m≤2⋅105) — the number of nobles and number of original friendships respectively.

The next mm lines each contain the integers uu and vv (1≤u,v≤n1≤u,v≤n, u≠vu≠v), describing a friendship. No friendship is listed twice.

The next line contains the integer qq (1≤q≤2⋅1051≤q≤2⋅105) — the number of queries.

The next qq lines contain the queries themselves, each query has one of the following three formats.

• 11 uu vv (1≤u,v≤n1≤u,v≤n, u≠vu≠v) — add a friendship between uu and vv. It is guaranteed that uu and vv are not friends at this moment.
• 22 uu vv (1≤u,v≤n1≤u,v≤n, u≠vu≠v) — remove a friendship between uu and vv. It is guaranteed that uu and vv are friends at this moment.
• 33 — print the answer to the process described in the statement.

Output

For each type 33 query print one integer to a new line. It is guaranteed that there will be at least one type 33 query.

题目大意：把n个人按照给出的关系相连，形成关系网，允许进行三个操作，1.添加新的关系， 2.断绝两个人的关系。 3.每次杀死关系中最弱小的一个，直到剩余人都相互孤立，求出最后剩余人数。

目标：杀死关系户

解题思路：势力小的人指向势力大的人，用有向图的思想，有人指向自己就是入度，自己只想别人就是出度。

读入和添加关系操作：每次只记录较小势力的那个人的出度增加了1，由于势力小的人指向势力大的人；并把该人加入到set中，记录为将被暗杀的人， 用set可以避免被重复记录。

输出剩余人数操作：最后剩余人数一定为 初始总人数 - 要被暗杀的人；

断绝关系操作：首先找到两个中势力较小的那个人，由于断绝了它与势力较大的那个人的关系，那么它可以仰仗的大佬少了一个，出度减一，并在set中搜索这个人并删除他，因为断绝了这段关系，他就孤立了，就不是关系户了，就不用被杀了。

#include <bits/stdc++.h>using namespace std;
const int N = 2e5+10;
int f[N];
set<int> se;
int main()
{int n, m;cin>>n>>m;for(int i = 1; i<=m; i++){int a, b;cin>>a>>b;int lower = min(a, b);f[lower]++;se.insert(lower);}int q;cin>>q;for(int i = 1; i<= q; i++){int qu;cin>>qu;if(qu == 1){int a, b;cin>>a>>b;int lower = min(a, b);f[lower]++;se.insert(lower);}else if(qu == 2){int a, b;cin>>a>>b;int lower = min(a, b);f[lower]--;if(f[lower] == 0) se.erase(lower);}else{cout<<n - se.size()<<endl;}}return 0;
}