QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #71807 | #2585. 原题识别 | He_Ren | 100 ✓ | 1148ms | 31252kb | C++23 | 10.5kb | 2023-01-12 01:20:07 | 2023-01-12 01:21:57 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAXN = 1e5 + 5;
const int MAXM = 2e5 + 5;
inline int read(void) {
int res = 0;
char c = getchar();
while (c < '0' || c > '9')
c = getchar();
while (c >= '0' && c <= '9')
res = res * 10 + c - '0', c = getchar();
return res;
}
namespace Gen {
unsigned int SA, SB, SC;
unsigned int Rand(void) {
SA ^= SA << 16;
SA ^= SA >> 5;
SA ^= SA << 1;
unsigned int t = SA;
SA = SB;
SB = SC;
SC ^= t ^ SA;
return SC;
}
}
struct Segment_Tree {
ll sum[MAXN << 2], tag[MAXN << 2];
#define ls(u) ((u)<<1)
#define rs(u) ((u)<<1|1)
#define lson(u) ls(u),l,mid
#define rson(u) rs(u),mid+1,r
inline void push_up(int u) {
sum[u] = sum[ls(u)] + sum[rs(u)];
}
inline void upd(int u, ll k, int len) {
sum[u] += len * k;
tag[u] += k;
}
inline void push_down(int u, int len) {
if (tag[u]) {
upd(ls(u), tag[u], (len + 1) >> 1);
upd(rs(u), tag[u], len >> 1);
tag[u] = 0;
}
}
void build(int u, int l, int r) {
sum[u] = tag[u] = 0;
if (l == r)
return;
int mid = (l + r) >> 1;
build(lson(u));
build(rson(u));
}
void add(int u, int l, int r, int ql, int qr, ll k) {
if (ql <= l && r <= qr) {
upd(u, k, r - l + 1);
return;
}
push_down(u, r - l + 1);
int mid = (l + r) >> 1;
if (ql <= mid)
add(lson(u), ql, qr, k);
if (mid < qr)
add(rson(u), ql, qr, k);
push_up(u);
}
ll getsum(int u, int l, int r, int ql, int qr) {
if (ql <= l && r <= qr)
return sum[u];
push_down(u, r - l + 1);
int mid = (l + r) >> 1;
if (ql <= mid && mid < qr)
return getsum(lson(u), ql, qr) + getsum(rson(u), ql, qr);
else
return ql <= mid ? getsum(lson(u), ql, qr) : getsum(rson(u), ql, qr);
}
int n;
inline void build(int _n) {
n = _n;
build(1, 1, n);
}
inline void add(int ql, int qr, ll k) {
if (ql <= qr)
add(1, 1, n, ql, qr, k);
}
inline ll getsum(int ql, int qr) {
return ql <= qr ? getsum(1, 1, n, ql, qr) : 0;
}
};
struct Query {
int type, u, v;
Query(void) {}
Query(int _type, int _u, int _v): type(_type), u(_u), v(_v) {}
};
int anc[MAXN], a[MAXN], pos[MAXN];
Query qs[MAXM];
ll res[MAXM];
void solve(void) {
int n = read(), d = read();
Gen::SA = read();
Gen::SB = read();
Gen::SC = read();
for (int i = 2; i <= d; ++i)
anc[i] = i - 1;
for (int i = d + 1; i <= n; ++i)
anc[i] = Gen::Rand() % (i - 1) + 1;
for (int i = 1; i <= n; ++i)
a[i] = Gen::Rand() % n + 1;
// printf("n = %d, d = %d\n",n,d);
// for(int i=1; i<=n; ++i) printf("anc[%d] = %d,\ta[%d] = %d\n",i,anc[i],i,a[i]);
for (int i = 1; i <= d; ++i)
pos[i] = i;
for (int i = d + 1; i <= n; ++i)
pos[i] = pos[anc[i]];
static int dep[MAXN];
for (int i = 1; i <= d; ++i)
dep[i] = 0;
for (int i = d + 1; i <= n; ++i)
dep[i] = dep[anc[i]] + 1;
auto lca = [&](int u, int v) {
while (dep[u] > dep[v])
u = anc[u];
while (dep[v] > dep[u])
v = anc[v];
while (u != v)
u = anc[u], v = anc[v];
return u;
};
static vector<int> qid[MAXN];
for (int i = 1; i <= d; ++i)
qid[i].clear();
int m = read();
for (int i = 1; i <= m; ++i) {
int type = read(), u = read(), v = read();
if (pos[u] > pos[v])
swap(u, v);
qs[i] = Query(type, u, v);
qid[pos[v]].push_back(i);
}
memset(res, 0, (m + 1) << 3);
static int nxt[MAXN], lst[MAXN];
fill(lst + 1, lst + n + 1, d + 1);
for (int i = d; i >= 1; --i)
nxt[i] = lst[a[i]], lst[a[i]] = i;
static vector<int> occ[MAXN];
for (int i = 1; i <= n; ++i)
occ[i] = {0};
for (int i = 1; i <= d; ++i)
occ[a[i]].push_back(i);
for (int i = 1; i <= n; ++i)
occ[i].push_back(d + 1);
static Segment_Tree sumk, sumb;
sumk.build(d);
sumb.build(d);
for (int i = 1; i <= n; ++i)
sumk.add(lst[i], d, 1);
fill(lst + 1, lst + n + 1, 0);
for (int RR = 1; RR <= d; ++RR) {
sumk.add(lst[a[RR]] + 1, RR - 1, 1);
sumb.add(lst[a[RR]] + 1, RR - 1, -RR + 1);
lst[a[RR]] = RR;
for (int i : qid[RR]) {
int type = qs[i].type, u = qs[i].u, v = qs[i].v;
int l = pos[u], r = pos[v];
static int bak[MAXN], sta[MAXN], cnt = 0, tp = 0;
auto pushbak = [&](int x) {
if (++bak[x] == 1)
++cnt;
sta[++tp] = x;
};
auto roll = [&](int save) {
while (tp > save)
if (--bak[sta[tp--]] == 0)
--cnt;
};
if (type == 1) {
if (l == r) {
int uv = lca(u, v);
pushbak(a[uv]);
for (; u != uv; u = anc[u])
pushbak(a[u]);
for (; v != uv; v = anc[v])
pushbak(a[v]);
res[i] = cnt;
} else {
for (; dep[u]; u = anc[u])
if (lst[a[u]] < l)
pushbak(a[u]);
for (; dep[v]; v = anc[v])
if (lst[a[v]] < l)
pushbak(a[v]);
res[i] = cnt + sumk.getsum(l, l);
}
} else { //(type == 2)
vector<int> A, B;
for (int t = u; dep[t]; t = anc[t])
A.push_back(t);
for (int t = v; dep[t]; t = anc[t])
B.push_back(t);
A.push_back(pos[u]);
reverse(A.begin(), A.end());
B.push_back(pos[v]);
reverse(B.begin(), B.end());
// Part 1
{
static int oth[MAXN];
int mid = 0;
if (l == r) {
while (mid + 1 < (int)A.size() && mid + 1 < (int)B.size() && A[mid + 1] == B[mid + 1])
++mid;
for (int sw = 1; sw <= 2; ++sw, swap(A, B)) {
int cur = 0;
for (int j = (int)A.size() - 1; j >= 1; --j) {
int x = a[A[j]];
if (bak[x])
cur += oth[x] - j;
else
cur += (int)A.size() - j, pushbak(x);
oth[x] = j;
if (j <= mid)
res[i] += cur;
}
roll(0);
}
res[i] -= mid;
pushbak(a[A[mid]]);
res[i] += ((ll)A.size() - (mid + 1)) * ((ll)B.size() - (mid + 1));
} else {
res[i] += sumk.getsum(l, l) * ((ll)A.size() - 1) * ((ll)B.size() - 1);
}
for (int j = mid + 1; j < (int)A.size(); ++j) {
int x = a[A[j]];
if (l != r && lst[x] >= l)
continue;
if (!bak[x]) {
pushbak(x);
oth[x] = j;
res[i] += ((ll)A.size() - j) * ((ll)B.size() - (mid + 1));
}
}
for (int j = mid + 1; j < (int)B.size(); ++j) {
int x = a[B[j]];
if (l != r && lst[x] >= l)
continue;
if (bak[x] >= 2)
continue;
if (bak[x] == 0) {
pushbak(x);
oth[x] = -1;
res[i] += ((ll)B.size() - j) * ((ll)A.size() - (mid + 1));
} else if (oth[x] != -1) {
pushbak(x);
res[i] += ((ll)B.size() - j) * (oth[x] - (mid + 1));
}
}
roll(0);
}
// Part 2
{
ll bas = sumk.getsum(1, l);
for (int j = 1; j < (int)B.size(); ++j) {
int x = a[B[j]];
if (lst[x] < l && !bak[x]) {
pushbak(x);
bas += l - lst[x];
}
res[i] += bas;
}
roll(0);
}
{
ll bas = sumk.getsum(l, l) * r + sumb.getsum(l, l);
pushbak(a[A[0]]);
for (int j = 1; j < (int)A.size(); ++j) {
int x = a[A[j]];
if (!bak[x]) {
pushbak(x);
auto it = lower_bound(occ[x].begin(), occ[x].end(), l);
int lx = *prev(it);
int rx = min(*it, r + 1);
bas += rx - lx - 1;
}
res[i] += bas;
}
roll(0);
}
// Part3
res[i] += sumk.getsum(1, l) * r + sumb.getsum(1, l);
}
roll(0);
}
sumk.add(RR + 1, nxt[RR] - 1, -1);
sumb.add(RR + 1, nxt[RR] - 1, RR);
}
for (int i = 1; i <= m; ++i)
printf("%lld\n", res[i]);
}
int main(void) {
int T = read();
while (T--)
solve();
return 0;
}
详细
Test #1:
score: 30
Accepted
time: 585ms
memory: 30268kb
input:
3 96399 70104 352607 503607 701698 198732 1 81463 87861 1 65504 83230 1 79936 87804 1 88830 88166 1 77973 44777 1 51799 44835 1 39775 61727 1 83170 89320 1 42936 24414 1 69822 72892 1 55122 88684 1 72042 54083 1 72498 89884 1 77599 46486 1 39184 62507 1 72082 59829 1 86411 83538 1 58199 47993 1 5312...
output:
45127 5737 5085 19923 18544 6711 19611 19417 16916 24479 22644 4887 14449 8162 20681 32179 18899 9711 18976 1580 42374 9017 17201 32000 6673 9735 33055 8807 15866 1438 27252 22947 5593 12337 25237 1885 1227 9374 40811 8363 8662 35623 14371 13956 12440 25347 3335 13005 31015 21176 15842 11330 9785 40...
result:
ok 590662 lines
Test #2:
score: 30
Accepted
time: 1148ms
memory: 31252kb
input:
3 93462 93462 198089 21092 490171 193889 2 66857 87119 2 66053 71005 1 38332 90069 2 88955 69730 2 44128 3255 2 43024 55262 2 56296 4917 2 64824 92036 1 35567 67670 2 55665 78399 2 47040 71743 2 44179 47165 2 19195 50559 1 39470 65813 2 47192 12119 2 87826 79538 2 35658 47364 1 46560 23526 2 91886 7...
output:
129514482565047 90552860056009 39770 140366242079658 2548889407192 36019588646234 5959587637653 138862401182438 27260 89122173277514 64418381921956 28322037491959 15304781080096 23011 9239208076161 159438659855932 22315524603837 20453 151786744147449 90755461139340 131500189927839 159232700655186 92...
result:
ok 578377 lines
Test #3:
score: 40
Accepted
time: 931ms
memory: 24608kb
input:
3 99069 21210 535118 478507 499996 192742 2 81987 60204 2 60168 56787 2 7020 58419 2 38493 50125 2 30099 66372 2 56061 16851 2 75140 25970 2 52005 43349 2 90823 30429 2 47148 40374 2 95394 30788 2 72437 70280 2 28664 97835 1 39731 70525 2 516 1729 2 76620 73423 2 61712 70480 2 31804 46927 2 30888 49...
output:
1919183134 9074765824 39903821891 27496108727 1199159402601 578554632061 18171350107 9365803115 464957486766 151286824704 508443655984 1023168094240 206600585106 12915 585684040 88622548437 522215022299 1084223397530 48460036608 5780 334295128974 447300213691 55864648016 1393901874904 7022 319553336...
result:
ok 584730 lines