A
可以发现线段树不能维护，因为查询时无法合并
l
o
g
log
log个区间的历史最小值。于是就可以用kd树。直接维护当前的值和历史最小值就行了。合并很简单。详见代码。
#include <bits/stdc++.h>
using namespace std;
inline void read(int &x) {
char ch; while(!isdigit(ch=getchar()));
for(x=ch-'0';isdigit(ch=getchar());x=x*10+ch-'0');
}
typedef long long LL;
const int MAXN = 100005;
int n, m, a[MAXN], id[MAXN];
LL ps[MAXN];
struct node{
LL sum, ans;
node(LL s=0):sum(s), ans(s){}
inline void operator +=(const node &v) { ans = min(ans, sum + v.ans), sum += v.sum; }
};
struct kdt { int x[2], mn[2], mx[2], ch[2], fa; node val, lz; }p[MAXN];
int DD, rt;
inline bool cmp(const int &i, const int &j) { return p[i].x[DD] < p[j].x[DD]; }
void build(int &i, int l, int r, int D) {
if(l > r) { i = 0; return; }
int mid = (l + r) >> 1; DD = D;
nth_element(id + l, id + mid, id + r + 1, cmp);
i = id[mid];
build(p[i].ch[0], l, mid-1, D^1);
build(p[i].ch[1], mid+1, r, D^1);
p[p[i].ch[0]].fa = p[p[i].ch[1]].fa = i;
for(int j = 0; j < 2; ++j) if(p[i].ch[j])
for(int k = 0; k < 2; ++k)
p[i].mn[k] = min(p[i].mn[k], p[p[i].ch[j]].mn[k]),
p[i].mx[k] = max(p[i].mx[k], p[p[i].ch[j]].mx[k]);
}
inline void giv_val(int i, node v) { p[i].val += v; }
inline void giv(int i, node v) { if(i) p[i].lz += v, giv_val(i, v); }
inline void pd(int i) {
if(p[i].lz.ans || p[i].lz.sum) {
giv(p[i].ch[0], p[i].lz);
giv(p[i].ch[1], p[i].lz);
p[i].lz = node();
}
}
void ins(int i, int mn[2], int mx[2], int v) {
if(!i || mn[0] > p[i].mx[0] || mx[0] < p[i].mn[0] || mn[1] > p[i].mx[1] || mx[1] < p[i].mn[1]) return;
if(mn[0] <= p[i].mn[0] && p[i].mx[0] <= mx[0] && mn[1] <= p[i].mn[1] && p[i].mx[1] <= mx[1]) { giv(i, node(v)); return; }
pd(i);
if(mn[0] <= p[i].x[0] && p[i].x[0] <= mx[0] && mn[1] <= p[i].x[1] && p[i].x[1] <= mx[1]) giv_val(i, node(v));
ins(p[i].ch[0], mn, mx, v); ins(p[i].ch[1], mn, mx, v);
}
void pdp(int x) { if(p[x].fa) pdp(p[x].fa); pd(x); }
LL qry(int x) { pdp(x); return p[x].val.ans; }
int pos[MAXN], v[MAXN], tim[MAXN], cntm, cntq;
int main () {
read(n), read(m);
for(int i = 1; i <= n; ++i) read(a[i]), ps[i] = ps[i-1] + a[i];
for(int i = 1, op, x, y; i <= m; ++i) {
read(op), read(x), read(y);
if(op == 1) ++cntm, pos[cntm] = x, v[cntm] = y, tim[cntm] = cntq;
else {
++cntq; id[cntq] = cntq;
p[cntq].mn[0] = p[cntq].mx[0] = p[cntq].x[0] = x;
p[cntq].mn[1] = p[cntq].mx[1] = p[cntq].x[1] = y;
p[cntq].val = node(ps[y]-ps[x-1]);
}
}
build(rt, 1, cntq, 0);
int mn[2], mx[2];
for(int i = 1, j = 1; i <= cntq; ++i) {
for(; j <= cntm && tim[j] < i; ++j) {
mn[0] = 1, mx[0] = pos[j];
mn[1] = pos[j], mx[1] = n;
ins(rt, mn, mx, v[j]-a[pos[j]]);
a[pos[j]] = v[j];
}
printf("%lld\n", qry(i));
}
}
B
动态开点线段树。（水题考场上sb了。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
const int MAXM = MAXN * 100;
int n, a, b, c, m, q, rt, tot;
char T[MAXN];
int lc[MAXM], rc[MAXM], lz[MAXM];
void ins(int &i, int l, int r, int x, int y, int v) {
if(!i) i = ++tot;
if(x <= l && r <= y) { lz[i] += v; return; }
int mid = (l + r) >> 1;
if(x <= mid) ins(lc[i], l, mid, x, y, v);
if(y > mid) ins(rc[i], mid+1, r, x, y, v);
}
int qry(int i, int l, int r, int x) {
if(!i) return 0;
if(l == r) return lz[i];
int mid = (l + r) >> 1;
return lz[i] + (x <= mid ? qry(lc[i], l, mid, x) : qry(rc[i], mid+1, r, x));
}
void Modify(int l, int r, int v) {
if(l <= r) ins(rt, 0, n-1, l, r, v);
else {
ins(rt, 0, n-1, l, n-1, v);
ins(rt, 0, n-1, 0, r, v);
}
}
int main () {
scanf("%d%d%d%d%d", &n, &a, &b, &c, &m);
scanf("%s%d", T, &q);
for(int i = 0; i < m; ++i) {
if(T[i] == '1') {
if(0 < c) Modify((0+n-1ll*a*i%n)%n, (c-1+n-1ll*a*i%n)%n, 1);
}
else {
if(c < n) Modify((c+n-1ll*a*i%n)%n, (n-1+n-1ll*a*i%n)%n, 1);
}
}
int op, p;
while(q--) {
scanf("%d%d", &op, &p);
if(op == 1) printf("%d\n", qry(rt, 0, n-1, (1ll*a*p+b)%n));
else {
if(T[p] == '1') {
if(0 < c) Modify((0+n-1ll*a*p%n)%n, (c-1+n-1ll*a*p%n)%n, -1);
T[p] = '0';
}
else {
if(c < n) Modify((c+n-1ll*a*p%n)%n, (n-1+n-1ll*a*p%n)%n, -1);
T[p] = '1';
}
if(T[p] == '1') {
if(0 < c) Modify((0+n-1ll*a*p%n)%n, (c-1+n-1ll*a*p%n)%n, 1);
}
else {
if(c < n) Modify((c+n-1ll*a*p%n)%n, (n-1+n-1ll*a*p%n)%n, 1);
}
}
}
}
C
考试根本没看。也不算太难（仅仅是我不会的程度
最后的方程式递推式的
i
=
n
−
1
i=n-1
i=n−1时，递推
i
=
n
i=n
i=n是没有意义的，所以两个递推式对应两个方程，里面
v
a
l
i
+
1
,
∗
=
0
val_{i+1,*}=0
vali+1,∗=0。
注意 v a l 1 , 1 val_{1,1} val1,1和 v a l n − 1 , 0 val_{n-1,0} valn−1,0是特殊情况，所以对应递推式没有 1 n \frac 1n n1那一项。
最后答案要加上选起点的方案和贡献。
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
inline void read(int &x) {
char ch; while(!isdigit(ch=getchar()));
for(x=ch-'0';isdigit(ch=getchar());x=x*10+ch-'0');
}
const int mod = 1e9 + 7;
const int MAXN = 100005;
struct node {
LL a, b, c;
node(LL a=0, LL b=0, LL c=0):a(a), b(b), c(c){}
inline void adj() { a<0?a+=mod:0;b<0?b+=mod:0;c<0?c+=mod:0; }
inline node operator +(const node o)const { return node((a+o.a)%mod, (b+o.b)%mod, (c+o.c)%mod); }
inline node operator -(const node o)const { return node((a-o.a)%mod, (b-o.b)%mod, (c-o.c)%mod); }
inline node operator +(const LL o)const { return node(a, b, (c+o)%mod); }
inline node operator -(const LL o)const { return node(a, b, (c-o)%mod); }
inline node operator *(const LL o)const { return node(a*o%mod, b*o%mod, c*o%mod); }
}dp[MAXN][2];
vector<int>e[MAXN];
int n, fa[MAXN], sz[MAXN]; char A[MAXN];
LL f[MAXN], inv[MAXN], cf[2];
void dfs(int u) {
sz[u] = 1;
for(int v, i = e[u].size()-1; i >= 0; --i)
if((v=e[u][i])) {
dfs(v), sz[u] += sz[v];
f[u] += f[v] + sz[v];
}
}
void dfs2(int u) {
if(fa[u]) f[u] = f[fa[u]] + n - 2*sz[u];
for(int v, i = e[u].size()-1; i >= 0; --i)
if((v=e[u][i])) dfs2(v);
}
inline LL qpow(LL a, LL b) { LL re = 1; for(; b; b>>=1, a=a*a%mod)if(b&1)re=re*a%mod; return re; }
int main () {
read(n); scanf("%s", A+1); int cnt = 0;
for(int i = 1; i <= n; ++i) cnt += A[i] == '1';
inv[0] = inv[1] = 1;
for(int i = 2; i <= n; ++i) read(fa[i]), e[fa[i]].push_back(i), inv[i] = (mod-mod/i)*inv[mod%i]%mod;
dfs(1), dfs2(1);
dp[1][0] = node(1, 0, 0); dp[1][1] = node(0, 1, 0);
for(int i = 1; i < n; ++i)
dp[i+1][1] = (dp[i][1] * n - (i!=1) - dp[i-1][1] * (i-1) - dp[i-1][0]) * inv[n-i], dp[i+1][1].adj(),
dp[i+1][0] = (dp[i][0] * n - 1 - dp[i-1][0] * i - dp[i+1][1]) * inv[n-i-1], dp[i+1][0].adj();
node X = dp[n-1][1] * n - 1 - dp[n-2][1] * (n-2) - dp[n-2][0]; X.adj();
node Y = dp[n-1][0] * n - dp[n-2][0] * (n-1); Y.adj();
//X = 0, Y = 0
LL t = X.b * qpow(Y.b, mod-2) % mod, x = (Y.c*t - X.c) % mod * qpow((X.a - Y.a*t) % mod, mod-2) % mod;
t = X.a * qpow(Y.a, mod-2) % mod; LL y = (Y.c*t - X.c) % mod * qpow((X.b - Y.b*t) % mod, mod-2) % mod;
cf[0] = cf[1] = 0;
for(int i = 0; i < 2; ++i) (cf[i] += dp[cnt][i].a * x + dp[cnt][i].b * y + dp[cnt][i].c) %= mod;
LL ans = 0, sum = 0;
for(int i = 1; i <= n; ++i) (ans += f[i] % mod * cf[A[i]=='1']) %= mod, (sum += f[i] % mod) %= mod;
ans = (ans * inv[n] % mod + sum * inv[n] % mod * inv[n]) % mod;
printf("%lld\n", ans);
}
扫一扫
1047
被折叠的 条评论
为什么被折叠?
到【灌水乐园】发言
