TOJ 512. 樓層交換
===
###### tags: `Ans`

> 有一個序列 1...n
有兩種操作
1.swap(a,b) 把兩個東西互換
2.recorver(l,r)
l<=i<=r
如果這個位置 i 上不是 i
那就把位置 i 上的東西跟 i swap, 並且記有效次數1
請輸出每一次操作 2 的有效次數
N=5e5, Q=5e5

---
事實上假如 swap 操作 a 次
最多弄亂 2a 個東西
所以全部的 recover 操作最多做 2a 次即可

---
對於 l<=i<=r 找出所有 ouo[i] != i, 維護一個 set s
其中元素 k 代表 ouo[k]!=k
每當區間操作 用 lower_bound 把全部區間內數 k 拔出來放
然後 set 在 swap 的時候維護

---

#include <bits/stdc++.h>
#define akiyama ios::sync_with_stdio(0), cin.tie(0);
#define all(x) x.begin(), x.end()
#define exi(x,s) (s.find(x) != x.end())
#define mem(a,x) memset(a,x,sizeof(a))
#define pb push_back
#define uset unordered_set
#define umap unordered_map
#define de(x) cout << #x << '=' << x << ", "
#define dend cout << "\n"
typedef long long ll;
using namespace std;
const int INF=0x7f7f7f7f, N = 5e5+10;

int ouo[N], pos[N], n, q;
set<int> s;
vector<int> v;

inline void print()
{
	cout << "ouo: ";
	for (int i=1; i<=n; i++) cout << ouo[i] << ' ';
	cout << '\n';
	cout << "pos: ";
	for (int i=1; i<=n; i++) cout << pos[i] << ' ';
	cout << '\n';
	cout << "dif pos: ";
	for (auto x: v) cout << x << ' ';
	cout << '\n';
}

inline void mswap (int a, int b)
{
	swap(pos[ouo[a]],pos[ouo[b]]);
	swap(ouo[a],ouo[b]);
	if (ouo[a] == a) s.erase(a);
	else s.insert(a);
	if (ouo[b] == b) s.erase(b);
	else s.insert(b);
}
inline void recover(int l, int r)
{
	int res = 0;
	v.clear();
	auto beg = s.lower_bound(l);
	auto ed = s.upper_bound(r);
	for (auto it = beg; it!=ed; it++) v.pb(*it);
	for (auto t: v)
		if (ouo[t]!=t)
			mswap(t,pos[t]), res++;
	cout << res << '\n';
}
int main()
{
	akiyama;
	cin >> n >> q;
	for (int i=1; i<=n; i++) ouo[i] = i, pos[i] = i;
	for (int i=0,opr,a,b; i<q; i++)
	{
		cin >> opr >> a >> b;
		if (opr == 1) mswap(a,b);
		else recover(a,b);
	}
}