c++ STL set 用法簡介

首先是頭檔案

#include<set>
//萬金油
#include<bits/stdc++.h>
           

然後是建立啦

set<element_type> name;
//element_type表示你想要儲存的資料類型
//name表示這個set的名字，當然，它可以是個數組
//例子：
set<int> s;// 這裡建立了一個set對象
set<int> a[10];//這裡建立了10個set對象
           

再然後就是插入元素啦

set<int> s;
s.insert(1);

//如果是s是數組的話也是一樣的：
set<int>s[10];
s[1].insert(1);
           

 再然後是删除啦

set<int> s;
//删除所有元素
s.clear()
//删除特定元素
s.erase(i);
           

然後是周遊和輸出啦

#include<bits/stdc++.h>
using namespace std;


int main()
{
	set<int> s;
	for(int i=0;i<10;i++)
	s.insert(i);
	s.erase(5);
    //注意用auto，讓it從s.begin() 開始，結束辨別是it指向s.end，注意不能用<哦，因為it是個指針捏
	for(auto it = s.begin();it!=s.end();it++)
		cout<<*it<<endl;
} 
           

最後是一些常用的方法：

set<int>s;

int flag = s.count(i);//計算s中i的個數，傳回1表示存在i，傳回0表示不存在i

//下面的函數傳回的是一個指針哦，如果想知道傳回的數具體是幾的話，可以醬紫：int num=*it;
auto it = s.size()//表示s中元素的個數，比較常用的一個方法，不僅是在set中
auto it = s.lower_bound(i)//在s中尋找第一個大于等于i的元素
auto it = s.upper_bound(i)//在s中尋找第一個比i大的元素
auto it = s.equal_range(i)//這個我也看不懂捏，不過好像也不怎麼用捏
           

例題：

B. Hossam and Friends

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

Hossam makes a big party, and he will invite his friends to the party.

He has nn friends numbered from 11 to nn. They will be arranged in a queue as follows: 1,2,3,…,n1,2,3,…,n.

Hossam has a list of mm pairs of his friends that don't know each other. Any pair not present in this list are friends.

A subsegment of the queue starting from the friend aa and ending at the friend bb is [a,a+1,a+2,…,b][a,a+1,a+2,…,b]. A subsegment of the queue is called good when all pairs of that segment are friends.

Hossam wants to know how many pairs (a,b)(a,b) there are (1≤a≤b≤n1≤a≤b≤n), such that the subsegment starting from the friend aa and ending at the friend bb is good.

Input

The input consists of multiple test cases. The first line contains a single integer tt (1≤t≤2⋅1041≤t≤2⋅104), the number of test cases. Description of the test cases follows.

The first line of each test case contains two integer numbers nn and mm (2≤n≤1052≤n≤105, 0≤m≤1050≤m≤105) representing the number of friends and the number of pairs, respectively.

The ii-th of the next mm lines contains two integers xixi and yiyi (1≤xi,yi≤n1≤xi,yi≤n, xi≠yixi≠yi) representing a pair of Hossam's friends that don't know each other.

Note that pairs can be repeated.

It is guaranteed that the sum of nn over all test cases does not exceed 105105, and the sum of mm over all test cases does not exceed 105105.

Output

For each test case print an integer — the number of good subsegments.

Example

input

Copy

2

3 2

1 3

2 3

4 2

1 2

2 3

output

Copy

4
5
      

Note

In the first example, the answer is 44.

The good subsegments are:

[1]

[2]

[3]

[1, 2]

In the second example, the answer is 55.

The good subsegments are:

[1]

[2]

[3]

[4]

[3, 4]

#include<bits/stdc++.h>
using namespace std;
#define int long long

set<int> s[100005]; 

signed main()
{
	int t;
	cin>>t;
	while(t--)
	{
		int n,m;
		cin>>n>>m;
		for(int i=1;i<=n;i++)
			s[i].clear();
		while(m--)
		{
			int a,b;
			cin>>a>>b;
			s[a].insert(b);
			s[b].insert(a);
		}
		int y=n;
		int ans=0;
		for(int i=n;i>=1;i--)
		{
			auto it = s[i].lower_bound(i);
			if(it!=s[i].end())
				y=min(y,*it-1);
			ans+=(y-i+1);
		}
		cout<<ans<<endl;
	}
	return 0;
}