# Codeforces Round #672 (Div. 2)

#### T1

A题给我们一个数列，每次可以交换相邻元素的位置，问我们能不能在 $$\frac{n(n-1)}{2}-1$$ 次操作内将元素调整为不下降序列。

#### T2

B题也是给出一个数列，要求求出满足 $$i < j$$$$a_i\ \oplus\ a_j < a_i\ \&\ a_j$$ 的数对的个数。

#### T3——1

C题分为 $$\text{easy version}$$$$\text{hard version}$$,我只会 $$\text{easy version}$$ \kk

$$f_i = \max(a_i,a_i+\max\limits_{j=1}^{j<i}g_j)$$

$$g_i = -a_i+\max\limits_{j=1}^{j<i}f_j$$

$$f_i = \max(a_i,f_{i-1},a_i+g_{i-1})$$
$$g_i = \max(g_{i-1},-a_i+f_{i-1})$$

$$f = \max(a_i,f,a_i+g)$$
$$g = \max(g,f-a_i)$$

#### T4

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#define ll long long
using namespace std;

int read()
{
int a = 0,x = 1;
char ch = getchar();
while(ch > ‘9‘ || ch < ‘0‘){
if(ch == ‘-‘) x = -1;
ch = getchar();
}
while(ch >= ‘0‘ && ch <= ‘9‘){
a = a*10 + ch-‘0‘;
ch = getchar();
}
return a*x;
}
const int P=998244353,N = 1e6+7;
struct node {
int l,r;
friend bool operator < (node a,node b) {return a.r > b.r;}
}arr[N];
bool cmp(node a,node b)
{
return a.l < b.l;
}
int n,m;
priority_queue<node>q;
ll fpow(ll a,ll x)
{
if(x == 0) return 1;
if(x == 1) return a;
ll tmp = fpow(a,x/2);
if(x&1) return tmp*tmp%P*a%P;
else return tmp*tmp%P;
}
ll f[N];
ll C(ll a,ll b)
{
return f[a]*fpow(f[b],P-2)%P*fpow(f[a-b],P-2)%P;
}

int main()
{
n = read(),m = read();
f[0] = 1;
for(int i = 1;i <= n;i ++) f[i] = f[i-1]*i%P;
for(int i = 1;i <= n;i ++) {
arr[i].l = read(),arr[i].r = read();
}
ll ans = 0;
sort(arr+1,arr+1+n,cmp);
for(int i = 1;i <= n;i ++) {
while(!q.empty() && q.top().r < arr[i].l) q.pop();
int tmp = q.size();
//	printf("%d \n",tmp);
if(tmp+1>=m) {
(ans += C(tmp,m-1)) %= P;
}
q.push(arr[i]);
}
printf("%lld\n",ans);
}


Codeforces Round #672 (Div. 2)

(0)
(0)

© 2014 bubuko.com 版权所有 鲁ICP备09046678号-4