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