http://codeforces.com/contest/1284
C. New Year and Permutation
题意：给定n，问1到n的所有排列的满足区间最大值减最小值等于区间长度-1的区间数量之和。
看到区间应该要想到枚举区间长度。
可以发现所需要的区间就是满足区间内所有数是连续的一段。
在固定长度下，先枚举区间的位置，以及区间内是哪一段数字，再把这些数字全排列，其他数字也全排列。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| #include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 3e5 + 10;
ll n, m, ans;
ll fac[N];
int main(){
scanf("%lld%lld", &n, &m);
fac[0] = 1;
for (int i = 1; i <= n; i++)fac[i] = fac[i - 1] * i%m;
for (ll i = 1; i <= n; i++) {
ll tmp = (n - i + 1)*(n - i + 1) % m*fac[i] % m*fac[n - i] % m;
ans = (ans + tmp) % m;
}
printf("%lld\n", ans);
return 0;
}
|
D. New Year and Conference
题意：有n个会议，2个场地A，B，每个会议在两个场地中都有对应区间。要求任意两个会议在两个场地中的相交性相同（是否相交）。若存在一对不相同，则输出NO。
两种做法。
扫描线+哈希
反证容易得到就是要求对于每个会议，与它相交的会议在两个场地相同，那么就是个区间相交问题，求出与这个区间相交的所有区间，可以用扫描线扫出来，但是要考虑怎么存起来以便两次结果对比，可以用哈希，给每个会议随机赋值，把所有相交的区间异或起来，据说这样碰撞的概率很低。
扫描线求相交区间：把每个区间拆成左右端点压入优先队列，每次取出时最左边的左端点优先，则相交的区间由两部分组成：左端点左边以及重叠处未闭合的左端点+区间内部的所有左端点。之所以要左端点优先是为了防止左端点与另一区间右端点重叠，这也应该要算作相交，但是如果让另一区间先闭合了，就没法算在“左端点左边未闭合的左端点”中了。
每次遇到左端点就计算答案。用前缀异或和维护出区间内的所有左端点，在用一个随着右端点闭合不断更新的变量维护左端点左边未闭合的区间。重叠的点也是可以分成这两部分的。
这样可以计算包含也视作相交的情况，而用set只能计算相交。
这样可以求出每个区间与它相交的所有区间，而如果只是要求相交区间个数，就直接给左右端点赋值1或-1即可，应为重叠点的遍历顺序并不影响计算个数结果。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
| #include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 3e5 + 10;
mt19937_64 mt(chrono::steady_clock::now().time_since_epoch().count());
int n;
typedef pair<int, int>pii;
int s[2][N], e[2][N];
unsigned ll r[N], ak[2][N], op[N];
void solve(int id) {
priority_queue<pii, vector<pii>, greater<pii> >q;
memset(op, 0, sizeof(op));
unsigned ll all = 0, open = 0;
for (int i = 1; i <= n; i++) {
q.push(pii(s[id][i], -i));
q.push(pii(e[id][i], i));
}
while (!q.empty()) {
int u = q.top().second; q.pop();
if (u < 0) {
op[-u] = open;
ak[id][-u] = all;
all ^= r[-u];
open ^= r[-u];
}
if (u > 0) {
open ^= r[u];
ak[id][u] ^= (all^op[u]);
}
}
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++)r[i] = mt();
for (int i = 1; i <= n; i++)
scanf("%d%d%d%d", &s[0][i], &e[0][i], &s[1][i], &e[1][i]);
solve(0); solve(1);
for (int i = 1; i <= n; i++)if (ak[0][i] ^ ak[1][i]) {
puts("NO"); return 0;
}
puts("YES");
return 0;
}
|
线段树
对于一个会议，要找到与它相交的会议，然后判断在另一个场地中是否相交。
左端点排序，对于每个会议，二分找到左端点在它的左右端点之间的会议，它们一定与当前区间相交，这些区间的下标（排序后）一定是连续的，可以线段树维护。
又因为相交等价于 不存在 s1>e2∣∣s2>e1 ，所以如果在另一个场地中存在 s1>e2∣∣e1<s2 的s或e值，则必定有不相交的区间，表明两边矛盾了。
所以按一边排序，再维护另一边s最大值和e最小值，若A中相交区间有s最大值大于当前区间e或e最小值小于当前区间s，则NO。
又因为这只是判断A中相交而B中不相交，还可能A中不相交而B中相交，所以交换A，B再判断一次。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
| #include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const int maxn = 1e5 + 10;
int n;
struct X
{
int sa, ea;
int sb, eb;
}a[maxn];
bool cmp(const X& a, const X& b) { return a.sa == b.sa ? a.ea < b.ea : a.sa < b.sa; }
#define mid ((l+r)>>1)
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
int emin[maxn << 2], smax[maxn << 2];
void pushup(int rt) {
emin[rt] = min(emin[rt << 1], emin[rt << 1 | 1]);
smax[rt] = max(smax[rt << 1], smax[rt << 1 | 1]);
}
void build(int l, int r, int rt) {
if (l == r) {
emin[rt] = a[l].eb;
smax[rt] = a[l].sb;
return;
}
build(lson); build(rson);
pushup(rt);
}
int query_e(int l, int r, int rt, int ql, int qr) {
if (ql <= l && qr >= r)return emin[rt];
int res = INF;
if (ql <= mid)res = min(res, query_e(lson, ql, qr));
if (qr > mid)res = min(res, query_e(rson, ql, qr));
return res;
}
int query_s(int l, int r, int rt, int ql, int qr) {
if (ql <= l && qr >= r)return smax[rt];
int res = 0;
if (ql <= mid)res = max(res, query_s(lson, ql, qr));
if (qr > mid)res = max(res, query_s(rson, ql, qr));
return res;
}
int tmp[maxn];
bool check() {
sort(a + 1, a + n + 1, cmp);
build(1, n, 1);
for (int i = 1; i <= n; i++)tmp[i] = a[i].sa; tmp[n + 1] = INF;
for (int i = 1; i <= n; i++) {
int pos = upper_bound(tmp + i + 1, tmp + n + 1, a[i].ea) - tmp;
if (tmp[pos] > a[i].ea)pos--;
if (query_s(1, n, 1, i + 1, pos) > a[i].eb || query_e(1, n, 1, i + 1, pos) < a[i].sb)return false;
}
return true;
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++)scanf("%d%d%d%d", &a[i].sa, &a[i].ea, &a[i].sb, &a[i].eb);
bool ok = check();
for (int i = 1; i <= n; i++)swap(a[i].sa, a[i].sb), swap(a[i].ea, a[i].eb);
ok &= check();
puts(ok ? "YES" : "NO");
return 0;
}
|
