一道好题——分治

一道好题应该有一个简洁的题面。
有一个长度为 n，初始全为 0 的序列 a，另有一个长度为 n 的序列 b，你希望将 a 变成 b，你可以执行如下两种操作：

1 x：将 a 中所有值为 x 的数 +1+1。
2 x：将 a 中下标为 x 的数 +1+1。

你不需要最小化操作次数，但只能使用最多 2000020000 次操作。

Input
第一行 一个正整数 n（1≤n≤1000）。
第二行  n 个非负整数 b1 ,⋯,bn （0≤ bi ≤n）描述序列 b。

Output
第一行一个整数 k 表示操作次数，你需要保证 0≤k≤20000。
之后 k 行每行两个整数 ,1 x 或 2 x，表示一次操作。对于 1 x 类型的操作，你需要保证 0≤x≤n，对于 2 x 类型的操作，你需要保证 1≤x≤n。

Input
4
2 4 3 1

Output
7
1 0
2 1
2 2
2 3
2 2
1 3
2 3
 

解析：

考虑分治，将所有相等的数压在一起先，然后每次让后半截先 +1 然后就可以提出后半截变成子问题了。做完后半截再做前半截。
这样大概是 nlogn 次。
要先进行 后半截的操作，避免 1类型操作。

这样造成的效果就是

1 1 1 1        1 1 1 1
1 1 2 1        1 1 2 1
1 1 2 2        1 2 2 1
1 1 3 3        1 3 3 1
1 1 3 4        1 4 3 1
1 2 3 4        2 4 3 1 
(排序后)      (原序列)

#include <bits/stdc++.h>
using namespace std;
#define int long long 
#define ios ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
typedef pair<int,int> PII;
const int N=2e6+10;
vector <PII> a;
vector <PII> ans;
int n;
void dfs(int l,int r,int now)
{
    if (l>r) return ;
    if (l==r)
    {
        while (now<a[l].first)
        {
            ans.push_back({2,a[l].second});
            now++;
        }
        return ;
    }
    else
    {
        while (now<a[l].first)
        {
            ans.push_back({1,now});
            now++;
        }
        int mid=l+r>>1;
        mid++;
        while (mid<=r&&a[mid].first<=now) mid++;
        if (mid<=r)
        {
            for (int i=mid;i<=r;i++) ans.push_back({2,a[i].second});
            dfs(mid,r,now+1);
            dfs(l,mid-1,now);
        }
    }
}
signed main()
{
    ios;
    cin>>n;
    for (int i=1;i<=n;i++)
    {
        int x;
        cin>>x;
        a.push_back({x,i});
    }
    sort(a.begin(),a.end());
    dfs(0,a.size()-1,0);
    cout<<ans.size()<<endl;
    for (auto x:ans) cout<<x.first<<" "<<x.second<<endl;
    return 0;
}