NOI模拟赛 #4

好像只有一个串串题可以做...

不会 dp 和数据结构啊 QAQ

10 + 20 + 100 = 130

一棵树，每个点有一个能量的最大容量 $l_i$ 和一个增长速度 $v_i$，每次可以选一个点，给 q 个时刻，每次把这个子树里和它距离不超过 k 的点的能量全都拿走，求每次拿走了多少

$n,q \leq 152501$

$Time \space Limit : 4s$

sol：

暴力常数小即可 70，常数大（我）只有 20

被 yyc 爆踩辣

（为什么你会这么熟练啊！你到底写过多少暴力了 QAQ

subtask 1.没有最大容量

对于每个点，将 (dfs序，深度) 作为二元组搞到矩形里，每次拿走的是一个矩形，

用 kd 树维护这些点即可

每次期望影响 $\sqrt{n}$ 个矩形和 $\sqrt{n}$ 个单点，复杂度 $O(卡不掉)$

subtask 2.一条链

构造一个关于“最后一次采摘时间"的序列

进行一次操作最多让这个序列的段数改变 2

就比如说有可能 002200 -> 044200 -> 554200

对于每个区间开一个三元组 $(l,r,x)$ 表示区间 $[l,r]$ 最后一次采摘的时间是 $x$

每次相当于每次拆开两个三元组，对它们中间的计算答案，显然中间的整段可以一起计算

现在的问题就是对于 $(l,r,x)$ 和 $(l,r,t)$ ，能拿到多少能量

分类讨论，如过 $\lceil \frac{l_i}{v_i} \rceil \leq t$，那就是 $\sum l_i$

否则就是$t \times \sum v_i$

用一个平衡树维护这些区间，然后用主席树查一遍区间有多少小于等于 $k$ 的元素就可以了

subtask 正解

还是 kd 树，搜出来一定是 $\sqrt{n}$ 个子树和 $\sqrt{n}$ 个单点，单点随便做一做

对于子树可以暴力递归下去找到“都被修改过”的子树

然后主席树合并，通过乱七八糟的复杂度分析大概是 $O(nlogn + q \sqrt{n} logn)$

这也是 $Time \space Limit : 4s$ 而且被暴力过了的原因

duliu

#include<cstdio>

#include<cstring>

#include<cctype>

#include<algorithm>

#define rep(i,s,t) for(int i=s;i<=t;i++)

#define dwn(i,s,t) for(int i=s;i>=t;i--)

using namespace std;

inline int read() {

    int x=,f=;char c=getchar();

    for(;!isdigit(c);c=getchar()) if(c=='-') f=-;

    for(;isdigit(c);c=getchar()) x=x*+c-'';

    return x*f;

}

#define L T[o].lc

#define R T[o].rc

typedef long long ll;

const int maxn=;

const int maxm=;

const int maxnode=;

const int inf=1e9;

int ls[maxnode],rs[maxnode],ToT;

int n,m,c[maxn],lim[maxn],first[maxn],to[maxn],dis[maxn],next[maxn],e;

int root[maxn],D;

ll sumk[maxnode],sumv[maxnode],ans;

struct Node {

    int mx[],mn[],x[],lc,rc,v,sum;

    bool operator < (const Node& ths) const {

        return x[D]<ths.x[D];

    }

}T[maxn];

void maintain(int o) {

    T[o].sum=T[L].sum+T[R].sum+;

    rep(c,,) {

        T[o].mx[c]=max(T[o].x[c],max(T[L].mx[c],T[R].mx[c]));

        T[o].mn[c]=min(T[o].x[c],min(T[L].mn[c],T[R].mn[c]));

    }

}

int setv[maxn],vali[maxn];

void pushdown(int o) {

    if(setv[o]>=) {

        setv[L]=setv[R]=vali[L]=vali[R]=setv[o];

        setv[o]=-;

    }

}

int merge(int x,int y) {

    if(!x) return y;

    if(!y) return x;

    int z=++ToT;

    sumv[z]=sumv[x]+sumv[y];sumk[z]=sumk[x]+sumk[y];

    ls[z]=merge(ls[x],ls[y]);rs[z]=merge(rs[x],rs[y]);

    return z;

}

void update(int& y,int x,int l,int r,int p,int v,int v2) {

    y=++ToT;sumk[y]=sumk[x]+v2;sumv[y]=sumv[x]+v;

    if(l==r) return;

    int mid=l+r>>;ls[y]=ls[x];rs[y]=rs[x];

    if(p<=mid) update(ls[y],ls[x],l,mid,p,v,v2);

    else update(rs[y],rs[x],mid+,r,p,v,v2);

}

void build(int& o,int l,int r,int cur) {

    if(l>r) return;D=cur;

    int mid=l+r>>;o=mid;nth_element(T+l,T+mid,T+r+);

    build(L,l,mid-,cur^);build(R,mid+,r,cur^);

    root[o]=merge(root[L],root[R]);update(root[o],root[o],,maxm,(lim[T[o].v]-)/c[T[o].v],lim[T[o].v],c[T[o].v]);

    maintain(o);

}

ll sk,sv;

void query(int o,int l,int r,int p) {

    if(!o) return;

    if(l==r) {sk+=sumk[o];sv+=sumv[o];}

    else {

        int mid=l+r>>;

        if(p<=mid) query(ls[o],l,mid,p);

        else sk+=sumk[ls[o]],sv+=sumv[ls[o]],query(rs[o],mid+,r,p);

    }

}

void calc(int o,int t) {

    if(!o) return;

    if(setv[o]>=) {

        sk=sv=;query(root[o],,maxm,t-setv[o]-);

        ans+=sv+(sumk[root[o]]-sk)*(t-setv[o]);

        setv[o]=-;

        return;

    }

    else {

        int x=T[o].v;

        ans+=min((ll)lim[x],(ll)(t-vali[o])*c[x]);

        vali[o]=t;

    }

    calc(L,t);calc(R,t);

}

void query(int o,int x1,int x2,int y,int t) {

    if(!o) return;

    if(T[o].mn[]>y||T[o].mx[]<x1||T[o].mn[]>x2) return;

    if(T[o].mx[]<=y&&T[o].mn[]>=x1&&T[o].mx[]<=x2) {

        calc(o,t);setv[o]=vali[o]=t;return;

    }

    pushdown(o);

    if(T[o].x[]<=y&&T[o].x[]>=x1&&T[o].x[]<=x2) {

        int x=T[o].v;

        ans+=min((ll)lim[x],(ll)(t-vali[o])*c[x]);

        vali[o]=t;

    }

    query(L,x1,x2,y,t);query(R,x1,x2,y,t);

}

void AddEdge(int u,int v,int w) {

    to[++e]=v;dis[e]=w;next[e]=first[u];first[u]=e;

}

int st[maxn],en[maxn],dep[maxn],cnt;

void dfs(int x) {

    st[x]=++cnt;

    for(int i=first[x];i;i=next[i]) {

        dep[to[i]]=dep[x]+dis[i];

        dfs(to[i]);

    }

    en[x]=cnt;

}

int main() {

    freopen("exploit.in","r",stdin);

    freopen("exploit.out","w",stdout);

    T[].mx[]=T[].mx[]=-inf;

    T[].mn[]=T[].mn[]=inf;

    n=read();int rt=;

    rep(i,,n) c[i]=read();

    rep(i,,n) lim[i]=read();

    rep(i,,n) {

        int f=read(),w=read();

        AddEdge(f,i,w);

    }

    dfs();

    rep(i,,n) T[i].x[]=st[i],T[i].x[]=dep[i],T[i].v=i;

    build(rt,,n,);

    m=read();

    while(m--) {

        int t=read(),u=read(),k=read();ans=;

        query(rt,st[u],en[u],k+dep[u],t);

        printf("%lld\n",ans);

    }

    return ;

}

给 $n$ 个点的坐标 $p_i$，每个点的参数 $a_i,b_i$和一个 $k$，第 $i$ 个点可以跳到标号为 $[i+1,i+k]$ 的点 $j$，代价为 $|p_i - p_j| \times b_i$，每到一个点，就会在这个点停留 $a_i$，求 $1$ 跳到 $n$ 的最小代价

$n \leq 152501$ 坐标范围不超过 $152501$

sol：

subtask 1.k=n

分类讨论

当 $p_i ≥ p_j$ 时，要求 $f_j - p_j \times b_j + p_i \times b_j$

设一条直线 $y = (b_j) x + (f_j - p_j \times b_j)$，把 $p_i$ 带进去就是答案

用一个李超树维护直线就可以了

#include<bits/stdc++.h>

#define LL long long

#define ls (x << 1)

#define rs ((x << 1) | 1)

using namespace std;

inline int read()

{

    int x = ,f = ;char ch = getchar();

    for(;!isdigit(ch);ch = getchar())if(ch == '-') f = -f;

    for(;isdigit(ch);ch = getchar())x =  * x + ch - '';

    return x * f;

}

const int maxn = ;

const LL inf = (1LL << );

int n,m,k;

LL dp[maxn];

int p[maxn],b[maxn],a[maxn];

vector<int> items[maxn << ];

int s[maxn << ],top;

struct Line{LL k,b;LL f(LL x){return k * x + b;}Line(){}Line(LL _k,LL _b){k = _k,b = _b;}}seg[maxn << ];

inline void build(int x,int l,int r)

{

    seg[x] = (Line){,inf};

    if(l == r)return;

    int mid = (l + r) >> ;

    build(ls,l,mid);build(rs,mid + ,r);

}

void rec(){while(top)seg[s[top--]] = (Line){,inf};}

inline void add_item(int x,int l,int r,int L,int R,int v)

{

    if(L <= l && r <= R){items[x].push_back(v);return;}

    int mid = (l + r) >> ;

    if(L <= mid)add_item(ls,l,mid,L,R,v);

    if(R > mid)add_item(rs,mid + ,r,L,R,v);

}

inline void add_line(int x,int l,int r,Line cur)

{

    s[++top] = x;

    if(l == r){if(cur.f(l) < seg[x].f(l))seg[x] = cur;return;}

    int mid = (l + r) >> ;

    if(cur.f(mid) < seg[x].f(mid))swap(cur,seg[x]);

    if(cur.f(l) < seg[x].f(l))add_line(ls,l,mid,cur);

    if(cur.f(r) < seg[x].f(r))add_line(rs,mid + ,r,cur);

}

void get_pos(int x,int l,int r,int L,int R,Line cur)

{

    if(L <= l && r <= R){add_line(x,l,r,cur);return;}

    int mid = (l + r) >> ;

    if(L <= mid)get_pos(ls,l,mid,L,R,cur);

    if(R > mid)get_pos(rs,mid + ,r,L,R,cur);

}

LL query(int x,int l,int r,int pos)

{

    if(l == r)return seg[x].f(pos);

    int mid = (l + r) >> ;

    if(pos <= mid)return min(seg[x].f(pos),query(ls,l,mid,pos));

    else return min(seg[x].f(pos),query(rs,mid + ,r,pos));

}

void solve(int x,int l,int r)

{

    int sz = items[x].size();

    for(int i=;i<sz;i++)

    {

        int targ = items[x][i];

        get_pos(,,m,,p[targ],Line(-b[targ],dp[targ] + (LL)p[targ] * b[targ]));

        get_pos(,,m,p[targ],m,Line(b[targ],dp[targ] - (LL)p[targ] * b[targ]));

    }

    if(sz != )

    {

        for(int i=l;i<=r;i++)dp[i] = min(dp[i],query(,,m,p[i]) + a[i]);

        rec();

    }

    int mid = (l + r) >> ;

    if(l == r)return;

    solve(ls,l,mid);solve(rs,mid + ,r);

}

signed main()

{

    freopen("cruise.in","r",stdin);

    freopen("cruise.out","w",stdout);

    n = read(),m = read(),k = read();

    for(int i=;i<=n;i++)p[i] = read(),dp[i] = inf;

    for(int i=;i<=n;i++)a[i] = read();

    for(int i=;i<=n;i++)b[i] = read();

    dp[] = a[];

    for(int i=;i<n;i++)add_item(,,n,i + ,min(i + k,n),i);

    build(,,m);solve(,,n);

    cout<<dp[n]<<endl;

}

subtask 正解

王 · 线段树分治 · 子健

线段树分治，然后就变成了上一个 subtask，撤销跟并查集一样，用一个栈维护所有操作，撤销那几个操作的影响即可

$O(nlog^3n)$ 看似不怎么可过，但李超树的两个 log 跟一个 log 差不多，所以可以过

定义 $f(S)$ 为字符串 $S$ 的 kmp 树上每个点的深度和（根的深度为 $1$），给 $q$ 个询问，每组一个 $m$ ，求 $\sum_{1 \leq l \leq r \leq m} f(S[l \cdots r])$

$|S| \leq 152501,q \leq 152501$

sol：

要求一个前缀和，差分一下，就是要求一个串后加一个新字符，kmp 树的深度和

于是再差分一下，变成了一个点在 kmp 树上的深度，这个能 fail 多少次就是多少，相当于它在这个前缀里出现的次数

然后就相当于一个字符串，每次添加一个字符，询问一个后缀出现了多少次

那就是后缀自动机板题，结尾相同的所有子串是一条 parent 树上的链，维护一下这条每个点有多少不同的串即可

然后就是一个链加 & 链查询

树链剖分 / LCT / 全局平衡二叉树即可

#include<bits/stdc++.h>

#define LL long long

using namespace std;

inline int read()

{

    int x = ,f = ;char ch = getchar();

    for(;!isdigit(ch);ch = getchar())if(ch == '-') f = -f;

    for(;isdigit(ch);ch = getchar())x =  * x + ch - '';

    return x * f;

}

const int maxn = ,mod = ;

char s[maxn];

int n,q;

int mxlen[maxn],fa[maxn],tr[maxn][];

int root,last,dfn;

inline void extend(int c)

{

    int p = last,np = last = ++dfn;

    mxlen[np] = mxlen[p] + ;

    while(p && !tr[p][c])tr[p][c] = np,p = fa[p];

    if(!p)fa[np] = root;

    else

    {

        int q = tr[p][c];

        if(mxlen[q] == mxlen[p] + )fa[np] = q;

        else

        {

            int nq = ++dfn;

            mxlen[nq] = mxlen[p] + ;memcpy(tr[nq],tr[q],sizeof(tr[nq]));fa[nq] = fa[q],fa[np] = fa[q] = nq;

            while(p && tr[p][c] == q)tr[p][c] = nq,p = fa[p];

        }

    }

}

int first[maxn],to[maxn << ],nx[maxn << ],cnt;

inline void add(int u,int v){to[++cnt] = v;nx[cnt] = first[u];first[u] = cnt;}

int size[maxn],dep[maxn],bl[maxn],pos[maxn],reh[maxn],_tms;

int anc[maxn];

inline void dfs1(int x)

{

    size[x] = ;

    for(int i=first[x];i;i=nx[i])

    {

        if(to[i] == anc[x])continue;

        anc[to[i]] = x;dep[to[i]] = dep[x] + ;

        dfs1(to[i]);size[x] += size[to[i]];

    }

}

inline void dfs2(int x,int col)

{

    int k = ;

    bl[x] = col;

    pos[x] = ++_tms;

    reh[_tms] = x;

    for(int i=first[x];i;i=nx[i])

        if(dep[to[i]] > dep[x] && size[to[i]] > size[k])k = to[i];

    if(!k)return;

    dfs2(k,col);

    for(int i=first[x];i;i=nx[i])

        if(dep[to[i]] > dep[x] && to[i] != k)dfs2(to[i],to[i]);

}

#define ls (x << 1)

#define rs ((x << 1) | 1)

int seg[maxn << ],tag[maxn << ],sum[maxn << ];

inline void pushup(int x){sum[x] = (sum[ls] + sum[rs]) % mod;}

inline void pushdown(int x)

{

    if(!tag[x])return;

    sum[ls] = (sum[ls] + tag[x] * seg[ls]) % mod;

    sum[rs] = (sum[rs] + tag[x] * seg[rs]) % mod;

    tag[ls] = (tag[ls] + tag[x]) % mod;

    tag[rs] = (tag[rs] + tag[x]) % mod;

    tag[x] = ;

}

inline void build(int x,int l,int r)

{

    if(l == r)

    {

        seg[x] = mxlen[reh[l]] - mxlen[fa[reh[l]]];

        return;

    }

    int mid = (l + r) >> ;

    build(ls,l,mid);build(rs,mid + ,r);

    seg[x] = (seg[ls] + seg[rs]) % mod;

}

inline void update(int x,int l,int r,int L,int R)

{

    if(L <= l && r <= R)

    {

        tag[x]++;

        sum[x] = (sum[x] + seg[x]) % mod;

        return;

    }

    pushdown(x);

    int mid = (l + r) >> ;

    if(L <= mid)update(ls,l,mid,L,R);

    if(R > mid)update(rs,mid + ,r,L,R);

    pushup(x);

}

inline int query(int x,int l,int r,int L,int R)

{

    if(L <= l && r <= R)return sum[x];

    pushdown(x);

    int mid = (l + r) >> ,ans = ;

    if(L <= mid)ans = (ans + query(ls,l,mid,L,R)) % mod;

    if(R > mid)ans = (ans + query(rs,mid + ,r,L,R)) % mod;

    return ans;

}

inline void modify(int x)

{

    while(bl[x] != bl[])

    {

        update(,,dfn,pos[bl[x]],pos[x]);

        x = anc[bl[x]];

    }update(,,dfn,pos[],pos[x]);

}

inline int ask(int x)

{

    int ans = ;

    while(bl[x] != bl[])

    {

        ans = (ans + query(,,dfn,pos[bl[x]],pos[x])) % mod;

        x = anc[bl[x]];

    }

    ans = (ans + query(,,dfn,pos[],pos[x])) % mod;

    return ans;

}

int hh[maxn];

int ret[maxn];

int main()

{

    freopen("zoo.in","r",stdin);

    freopen("zoo.out","w",stdout);

    root = last = ++dfn;

    scanf("%s",s + );

    n = strlen(s + );

    for(int i=;i<=n;i++)extend(s[i] - 'a');

    for(int i=;i<=dfn;i++)add(fa[i],i);

    dfs1(root);dfs2(root,root);

    build(,,dfn);

    int q = read();

    int ans = ,now = ,res = ;

    for(int i=;i<=n;i++)

    {

        now = tr[now][s[i] - 'a'];

        res = (res + ask(now) + i) % mod;

        ans = (ans + res) % mod;

        modify(now);

        ret[i] = ans;

    }

    for(int i=;i<=q;i++)

    {

        int x = read();

        printf("%d\n",ret[x]);

    }

}

巴特西

NOI模拟赛 #4

最新文章

热门文章