Mayor's posters（线段树散点）

线段树散点）"/>

Mayor's posters（线段树散点）

Mayor’s posters

参考大佬

代码：

#include<iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <string>
#include <cmath>
#include <stack>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <functional>
#include <ctime>
#include <iomanip>
#include <sstream>
#include <algorithm>
#define ll int
#define mes(x,y) memset(x,y,sizeof(x))
#define FAST_IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;
ll GCD(ll a, ll b) {//最大公约数return b == 0 ? a : GCD(b, a % b);
}
ll Power(ll a, ll b, ll p) { //计算(a^b)%p;ll ans = 1;while (b) {if (b & 1) //等价于b%2，判断b的奇偶性ans = ans * a % p; //如果为奇数，证明该位为1，需要乘上aa = a * a % p; //计算a^(2^i)b >>= 1; //等价于b/=2;}return ans;
}
bool isprime(int num)
{if (num == 2 || num == 3)return true;if (num % 6 != 1 && num % 6 != 5)return false;int t = sqrt((double)num);for (int i = 5; i <= t; i += 6){if (num % i == 0 || num % (i + 2) == 0)return false;}return true;
}
const ll INFF = 2000000;
const ll maxn = 1e6 + 10;
ll tree[maxn];
void Update(ll begin, ll end, ll value, ll l, ll r, ll flag) {if (begin <= l && end >= r) {tree[flag] = value;//cout << l << " " << r << " " << flag << " " << value << endl;//cout <<flag<<":"<< tree[flag] << endl;return;}//cout << l << " " << r << " " << flag << " " << value << endl;if (tree[flag]!=-1) {tree[flag * 2] = tree[flag * 2 + 1] = tree[flag];tree[flag] = -1;}ll t = (l + r) / 2;if (begin <= t)Update(begin, end, value, l, t, flag * 2);if (end > t)Update(begin, end, value, t + 1, r, flag * 2 + 1);
}
bool sum[20000000];
ll cou = 0;
void Query(ll begin, ll end, ll flag) {//cout << begin << " " << end << " " << flag << ":" << tree[flag] << endl;if (tree[flag] != -1) {if (sum[tree[flag]]) {cou++;sum[tree[flag]] = false;}return;}if (begin == end)return;ll t = (begin + end)/ 2;Query(begin, t, flag * 2);Query(t + 1, end, flag * 2 + 1);
}
int main() {FAST_IO;ll n, m, k, i, j, vb;while (cin >> k) {while (k--) {cin >> n;ll x[10040], y[10040];vector<ll>v;map<ll, ll>mm;for (i = 0; i < n; i++) {cin >> x[i] >> y[i];if (!mm[x[i]]) {v.push_back(x[i]);mm[x[i]]++;}if (!mm[y[i]]) {v.push_back(y[i]);mm[y[i]]++;}}sort(v.begin(), v.end());for (i = 1, j = v.size(); i < j; i++) {if (v[i] - v[i - 1] > 1) {v.push_back((v[i] + v[i - 1]) / 2 + (v[i] + v[i - 1]) % 2);}}sort(v.begin(), v.end());mes(tree, -1);for (i = 0; i < n; i++) {//	cout << x[i] << " " << y[i] << endl;//	cout << flag[x[i]] << " " << flag[y[i]] << endl << endl;ll l = lower_bound(v.begin(), v.end(), x[i]) - v.begin();ll r = lower_bound(v.begin(), v.end(), y[i]) - v.begin();Update(l+1, r+1, i + 1, 1, v.size(), 1);//cout << tree[16] << endl << endl;}cou = 0;mes(sum, true);Query(1, v.size(), 1);//	set<ll>::iterator it;//	for (it = sv.begin(); it != sv.end(); it++)cout << *it << " ";//	cout << endl;cout << cou << endl;}}
}