QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #78507 | #5425. Proposition Composition | APJifengc | ML | 3ms | 7784kb | C++14 | 7.1kb | 2023-02-19 11:03:59 | 2023-02-19 11:04:00 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 250005;
const int the_answer_to_life_the_universe_and_everything = 42;
int T, n, m;
int pre[MAXN], nxt[MAXN], siz[MAXN], root[MAXN], bl[MAXN], tot;
long long cnt;
struct SegmentTree {
struct Node {
int mn, mx;
int cnt[2], tag;
} t[MAXN << 2];
#define lc (i << 1)
#define rc (i << 1 | 1)
void tag(int i, int v) {
if (v == 1) {
t[i].cnt[1] = t[i].cnt[0], t[i].cnt[0] = 0;
} else {
t[i].cnt[0] = t[i].cnt[1] = 0;
}
t[i].tag += v;
}
void pushDown(int i) {
if (t[i].tag) {
tag(lc, t[i].tag);
tag(rc, t[i].tag);
t[i].tag = 0;
}
}
void pushUp(int i) {
t[i].mn = min(t[lc].mn, t[rc].mn);
t[i].mx = max(t[lc].mx, t[rc].mx);
t[i].cnt[0] = t[lc].cnt[0] + t[rc].cnt[0];
t[i].cnt[1] = t[lc].cnt[1] + t[rc].cnt[1];
}
void build(int i = 1, int l = 1, int r = n - 1) {
t[i].tag = 0;
if (l == r) {
t[i].cnt[0] = 1, t[i].cnt[1] = 0;
t[i].mn = pre[l], t[i].mx = nxt[l];
return;
}
int mid = (l + r) >> 1;
build(lc, l, mid);
build(rc, mid + 1, r);
pushUp(i);
}
void add(int a, int b, int i = 1, int l = 1, int r = n - 1) {
if (a <= l && r <= b) {
tag(i, 1);
return;
}
pushDown(i);
int mid = (l + r) >> 1;
if (a <= mid) add(a, b, lc, l, mid);
if (b > mid) add(a, b, rc, mid + 1, r);
pushUp(i);
// printf("%d [%d, %d] %d %d\n", i, l, r, t[i].cnt[0], t[i].cnt[1]);
}
void findL(int a, int b, int v, vector<pair<int, int>> &p, int i = 1, int l = 1, int r = n - 1) {
if (t[i].mn >= v) return;
if (l == r) {
p.push_back({ bl[l], l });
return;
}
int mid = (l + r) >> 1;
if (a <= mid) findL(a, b, v, p, lc, l, mid);
if (b > mid) findL(a, b, v, p, rc, mid + 1, r);
}
void findR(int a, int b, int v, vector<pair<int, int>> &p, int i = 1, int l = 1, int r = n - 1) {
if (t[i].mx <= v) return;
if (l == r) {
p.push_back({ bl[nxt[l]], nxt[l] });
return;
}
int mid = (l + r) >> 1;
if (a <= mid) findR(a, b, v, p, lc, l, mid);
if (b > mid) findR(a, b, v, p, rc, mid + 1, r);
}
void setPre(int d, int v, int i = 1, int l = 1, int r = n - 1) {
if (l == r) {
pre[i] = t[i].mn = v;
return;
}
pushDown(i);
int mid = (l + r) >> 1;
if (d <= mid) setPre(d, v, lc, l, mid);
else setPre(d, v, rc, mid + 1, r);
pushUp(i);
}
void setNxt(int d, int v, int i = 1, int l = 1, int r = n - 1) {
if (l == r) {
nxt[i] = t[i].mx = v;
return;
}
pushDown(i);
int mid = (l + r) >> 1;
if (d <= mid) setNxt(d, v, lc, l, mid);
else setNxt(d, v, rc, mid + 1, r);
pushUp(i);
}
} st;
long long calcAns(int m) {
long long ans = 0;
int zero = st.t[1].cnt[0], one = st.t[1].cnt[1];
// printf("zero = %d\n", zero);
// case 1: zero - m and zero - nonzero
ans += 1ll * zero * (n - 1 + m - zero);
// printf("case 1: %lld\n", 1ll * zero * (n - 1 + m - zero));
// case 2: one - m
ans += one;
// printf("case 2: %lld\n", one);
// case 3: nonzero - nonzero
ans += cnt;
// printf("case 3: %lld\n", cnt);
return ans;
}
void connect(int x, int y) {
st.setPre(y, x);
st.setNxt(x, y);
}
void disconnect(int x) {
int y = pre[x];
st.setPre(x, x);
st.setNxt(y, y);
}
void newList(vector<int> &a) {
++tot;
root[tot] = a[0];
siz[tot] = a.size();
for (int i : a) bl[i] = tot;
}
long long C(int x) {
return 1ll * x * (x - 1) / 2;
}
void cut(int p, int l) {
cnt -= C(siz[p]);
vector<int> v1, v2;
int p1 = root[p], p2 = l;
while (the_answer_to_life_the_universe_and_everything == 42) {
v1.push_back(p1), v2.push_back(p2);
int np1 = nxt[p1] == l ? p1 : nxt[p1];
int np2 = nxt[p2];
// printf("%d -> %d\n", p1, np1);
// printf("%d -> %d\n", p2, np2);
if (np1 == p1) {
newList(v1);
root[p] = l;
siz[p] -= v1.size();
break;
} else if (np2 == p2) {
newList(v2);
siz[p] -= v2.size();
break;
} else {
p1 = np1;
p2 = np2;
}
}
// printf("cut %d to [%d, %d]\n", p, siz[tot], siz[p]);
disconnect(l);
cnt += C(siz[tot]) + C(siz[p]);
}
void cut(int p, int l, int r) {
cnt -= C(siz[p]);
vector<int> v1, v2;
int p1 = root[p], p2 = l;
while (the_answer_to_life_the_universe_and_everything == 42) {
v1.push_back(p1), v2.push_back(p2);
int np1 = nxt[p1] == l ? r : nxt[p1];
int np2 = nxt[p2] == r ? p2 : nxt[p2];
if (np1 == p1) {
newList(v1);
root[p] = l;
siz[p] -= v1.size();
break;
} else if (np2 == p2) {
newList(v2);
siz[p] -= v2.size();
break;
} else {
p1 = np1;
p2 = np2;
}
}
int tmp = pre[l];
disconnect(l), disconnect(r), connect(tmp, r);
cnt += C(siz[tot]) + C(siz[p]);
}
int main() {
// freopen("L.in", "r", stdin);
scanf("%d", &T);
while (T--) {
scanf("%d%d", &n, &m);
if (n == 1) {
for (int i = 1; i <= m; i++) {
scanf("%*d%*d");
printf("0\n");
}
continue;
}
tot = 1;
cnt = C(n - 1);
root[1] = 1;
nxt[n - 1] = n - 1, pre[1] = 1;
siz[1] = n - 1;
for (int i = 1; i <= n - 1; i++) {
bl[i] = 1;
}
for (int i = 1; i < n - 1; i++) {
nxt[i] = i + 1, pre[i + 1] = i;
}
st.build();
for (int i = 1; i <= m; i++) {
int u, v; scanf("%d%d", &u, &v);
if (u == v) {
printf("%lld\n", calcAns(i));
continue;
}
if (u > v) swap(u, v);
v--;
st.add(u, v);
vector<pair<int, int>> pt;
st.findL(u, v, u, pt);
st.findR(u, v, v, pt);
sort(pt.begin(), pt.end());
// for (auto p : pt) {
// printf("(%d, %d) ", p.first, p.second);
// }
// printf("\n");
for (int i = 0; i < pt.size(); i++) {
if (i + 1 < pt.size() && pt[i].first == pt[i + 1].first) {
cut(pt[i].first, pt[i].second, pt[i + 1].second);
i++;
} else {
cut(pt[i].first, pt[i].second);
}
}
printf("%lld\n", calcAns(i));
}
}
return 0;
}
/*
15
12
3
2
*/
详细
Test #1:
score: 100
Accepted
time: 3ms
memory: 7784kb
input:
3 4 3 2 4 4 2 3 3 7 3 3 4 1 2 1 7 6 4 1 3 4 6 2 5 3 4
output:
6 5 6 21 24 10 15 12 3 2
result:
ok 10 numbers
Test #2:
score: -100
Memory Limit Exceeded
input:
45540 10 9 10 1 1 10 10 1 1 10 1 10 10 1 1 10 3 3 10 1 10 4 1 2 1 10 3 4 1 10 7 6 7 1 5 6 1 7 6 6 7 1 6 7 9 7 3 3 7 7 5 4 1 1 9 1 9 1 6 5 8 7 1 8 4 4 5 6 1 1 1 8 6 6 4 5 3 3 3 2 3 1 3 3 3 9 3 1 3 3 2 2 3 3 3 1 2 2 1 1 2 3 3 1 10 1 2 1 7 1 1 7 3 8 1 3 1 3 3 3 1 3 2 2 1 3 1 3 3 3 3 6 3 1 1 3 1 3 1 3 1...