Greetings

Problem - 1915F - Codeforces

题意

给一些(l,r)找到所有能够包含(l,r)的数目

引入

也就是找逆序对个数

要用到归并排序中的思想：

//https://www.luogu.com.cn/problem/P1216
#include<iostream>
#include<cstdio>
#include<stack>
#include<vector>
#include<algorithm>
#include<cmath>
#include<queue>
#include<cstring>
#include<map>
#include<set>
#include<vector>
#define int long long
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define  long long
#define PI acos(-1.0)
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
const int INF = 1e18 + 10;
const int N = 2e5 + 10;
const int M = 1e7 + 10;
const int mod = 1e9 + 7;
int n, m, k, ans;
int qcal(int a, int b) { int res = 1; while (b) { if (b & 1) res = res * a % mod; b >>= 1; a = a * a % mod; } return res; }
int a[N];
bool is_prime(int n) { if (n < 2) return false; for (int i = 2; i <= n / i; i++) { if (n % i == 0) { return false; } }return true; }
int b[N];
void merge(int l,int r)
{// 拆分if(l == r) return;int mid = l + r >> 1;merge(l,mid);merge(mid+1,r);// 合并int i = l,j = mid + 1,k = l;while(i <= mid && j <= r){if(a[i] <= a[j]) b[k ++] = a[i ++];else b[k ++] = a[j ++];}while(i <= mid) b[k ++] = a[i ++];while(j <= r) b[k ++] = a[j ++];for(i = l;i <= r;i ++) a[i] = b[i];
}void gzy()
{cin >> n;for(int i = 1;i <= n;i ++) cin >> a[i];merge(1,n);for(int i = 1;i <= n;i ++) cout << a[i] << ' ';puts("");
}
signed main()
{IOS;int _ = 1; while (_--) gzy();return 0;
}

思路

只需要加一个 sum += mid - i + 1;

code

#include<iostream>
#include<cstdio>
#include<stack>
#include<vector>
#include<algorithm>
#include<cmath>
#include<queue>
#include<cstring>
#include<map>
#include<set>
#include<vector>
#define int long long
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define  long long
#define PI acos(-1.0)
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
const int INF = 1e18 + 10;
const int N = 5e5 + 10;
const int M = 1e7 + 10;
const int mod = 1e9 + 7;
int n, m, k, ans;
int qcal(int a, int b) { int res = 1; while (b) { if (b & 1) res = res * a % mod; b >>= 1; a = a * a % mod; } return res; }
int a[N];
bool is_prime(int n) { if (n < 2) return false; for (int i = 2; i <= n / i; i++) { if (n % i == 0) { return false; } }return true; }
int b[N];
int sum = 0;
void merge(int l,int r)
{// 拆分if(l == r) return;int mid = l + r >> 1;merge(l,mid);merge(mid+1,r);// 合并int i = l,j = mid + 1,k = l;while(i <= mid && j <= r){if(a[i] <= a[j]){b[k ++] = a[i ++];}else {sum += mid - i + 1;b[k ++] = a[j ++];}}while(i <= mid) b[k ++] = a[i ++];while(j <= r) b[k ++] = a[j ++];for(i = l;i <= r;i ++) a[i] = b[i];
}void gzy()
{cin >> n;for(int i = 1;i <= n;i ++) cin >> a[i];merge(1,n);// for(int i = 1;i <= n;i ++) cout << a[i] << ' ';// puts("");cout << sum << endl;
}
signed main()
{IOS;int _ = 1; while (_--) gzy();return 0;
}

思路

就是对first排序之后 找到second中的逆序对个数

code

//https://www.luogu.com.cn/problem/P1216
#include<iostream>
#include<cstdio>
#include<stack>
#include<vector>
#include<algorithm>
#include<cmath>
#include<queue>
#include<cstring>
#include<map>
#include<set>  
#include<vector>
#define int long long
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define  long long
#define PI acos(-1.0)
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
const int INF = 1e18 + 10;
const int N = 5e5 + 10;
const int M = 1e7 + 10;
const int mod = 1e9 + 7;
int n, m, k, ans;
int qcal(int a, int b) { int res = 1; while (b) { if (b & 1) res = res * a % mod; b >>= 1; a = a * a % mod; } return res; }
PII d[N];
bool is_prime(int n) { if (n < 2) return false; for (int i = 2; i <= n / i; i++) { if (n % i == 0) { return false; } }return true; }
int a[N],b[N];
int sum = 0;
void merge(int l,int r)
{// 拆分if(l == r) return;int mid = l + r >> 1;merge(l,mid);merge(mid+1,r);// 合并int i = l,j = mid + 1,k = l;while(i <= mid && j <= r){if(a[i] <= a[j]){b[k ++] = a[i ++];   }else {sum += mid - i + 1;b[k ++] = a[j ++];}}while(i <= mid) b[k ++] = a[i ++];while(j <= r) b[k ++] = a[j ++];for(i = l;i <= r;i ++) a[i] = b[i];
}void gzy()
{sum = 0;cin >> n;for(int i = 1;i <= n;i ++) cin >> d[i].first >> d[i].second;sort(d+1,d+1+n);for(int i = 1;i <= n;i ++) a[i] = d[i].second;merge(1,n);cout << sum << endl;
}
signed main()
{IOS;int _ = 1; cin >> _;while (_--) gzy();return 0;
}