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;
}