首页 > 其他分享 >LOJ6119 「2017 山东二轮集训 Day7」国王

LOJ6119 「2017 山东二轮集训 Day7」国王

时间:2024-11-06 22:10:37浏览次数:2  
标签:fir fa int Day7 tp vis nex LOJ6119 2017

题意

给定一颗树,每个点有权值 \(1\) 和 \(-1\),称一条路径是好的当且仅当路径上所有点的权值和为 \(0\)。

求连续编号区间 \([l, r]\) 使得两个点都在 \([l, r]\) 的好路径比两个点都不在 \([l, r]\) 的好路径数严格多的方案数。

\(n \le 10 ^ 5\)。

Sol

两个端点都在区间内不好做,设一个区间的权值为 \(f_{[l, r]}\)。

因此答案为 \(\sum [f_{[l, r]} > f_{[1, l - 1] \cup [r + 1, n]}]\)。

集中注意力,考虑至少一个端点在区间内的情况,发现好像两边可以约掉!

具体地,至少一个端点在 \([l, r]\) 的方案数 等于 \(f_{[l, r]}\) 加上 有一个端点在 \([l, r]\) 一个端点在 \([1, l- 1] \cup [r + 1, n]\) 的方案数,于是直接约掉了。

考虑我们现在可以求出什么,设 \(g_i\) 表示一个端点为 \(i\) 的合法路径数,这个东西可以简单使用点分治求得。

最后因为合法区间具有单调性,直接双指针计算最小的合法区间即可。

复杂度 \(O(n \log n)\)。

Code

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <array>
#include <bitset>
#define ll long long
#define pii pair <int, int>
using namespace std;
#ifdef ONLINE_JUDGE

#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)
char buf[1 << 23], *p1 = buf, *p2 = buf, ubuf[1 << 23], *u = ubuf;

#endif
int read() {
    int p = 0, flg = 1;
    char c = getchar();
    while (c < '0' || c > '9') {
        if (c == '-') flg = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9') {
        p = p * 10 + c - '0';
        c = getchar();
    }
    return p * flg;
}
void write(ll x) {
    if (x < 0) {
        x = -x;
        putchar('-');
    }
    if (x > 9) {
        write(x / 10);
    }
    putchar(x % 10 + '0');
}
bool _stmer;

#define fi first
#define se second

const int N = 1e5 + 5, M = 2e5 + 5;

namespace G {

array <int, N> fir;
array <int, M> nex, to;

int cnt = 1;
void add(int x, int y) {
    cnt++;
    nex[cnt] = fir[x];
    to[cnt] = y;
    fir[x] = cnt;
}

} //namespace G

array <int, N> len, siz;
bitset <N> vis;

void dfs1(int x, int fa) {
    siz[x] = 1;
    for (int i = G::fir[x]; i; i = G::nex[i]) {
        if (vis[G::to[i]] || G::to[i] == fa) continue;
        dfs1(G::to[i], x), siz[x] += siz[G::to[i]];
    }
}

pii rt;

void dfs2(int x, int fa, int Rt) {
    int tp = 0;
    for (int i = G::fir[x]; i; i = G::nex[i]) {
        if (vis[G::to[i]] || G::to[i] == fa) continue;
        dfs2(G::to[i], x, Rt), tp = max(tp, siz[G::to[i]]);
    }
    tp = max(tp, siz[Rt] - siz[x]);
    if (tp < rt.fi) rt = make_pair(tp, x);
}

array <int, M> isl;
array <int, N> dis;

void dfs3(int x, int pl, int fa) {
    isl[dis[x]] += pl;
    for (int i = G::fir[x]; i; i = G::nex[i]) {
        if (vis[G::to[i]] || G::to[i] == fa) continue;
        dis[G::to[i]] = dis[x] + len[G::to[i]];
        dfs3(G::to[i], pl, x);
    }
}

array <int, N> f;

void dfs4(int x, int fa, int sum) {
    f[x] += isl[1e5 - sum];
    for (int i = G::fir[x]; i; i = G::nex[i]) {
        if (vis[G::to[i]] || G::to[i] == fa) continue;
        dfs4(G::to[i], x, sum + len[G::to[i]]);
    }
}


void solve(int x) {
    dis[x] = 1e5 + len[x];
    dfs3(x, 1, 0);
    f[x] += isl[1e5];
    for (int i = G::fir[x]; i; i = G::nex[i])
        if (!vis[G::to[i]])
            dfs3(G::to[i], -1, x), dfs4(G::to[i], x, len[G::to[i]]), dfs3(G::to[i], 1, x);
    dfs3(x, -1, 0);
}

void divide(int x) {
    rt = make_pair(2e9, 0);
    dfs1(x, 0), dfs2(x, 0, x);
    x = rt.se, vis[x] = 1, solve(x);
    for (int i = G::fir[x]; i; i = G::nex[i])
        if (!vis[G::to[i]]) divide(G::to[i]);
}

bool _edmer;
int main() {
    cerr << (&_stmer - &_edmer) / 1024.0 / 1024.0 << "MB\n";
    int n = read();
    for (int i = 1, x; i <= n; i++)
        x = read(), len[i] = x ? 1 : -1;
    for (int i = 2, x, y; i <= n; i++)
        x = read(), y = read(), G::add(x, y), G::add(y, x);
    divide(1);
    ll res = 0, sum = 0, ans = 0;
    for (int i = 1; i <= n; i++) res += f[i];
    for (int i = 1, lst = 1; i <= n; i++) {
        sum += f[i];
        while (lst < i && sum > res - sum) sum -= f[lst++];
        ans += lst - 1;
    }
    write(ans), puts("");
    return 0;
}

标签:fir,fa,int,Day7,tp,vis,nex,LOJ6119,2017
From: https://www.cnblogs.com/cxqghzj/p/18531164

相关文章

  • LOJ6118 「2017 山东二轮集训 Day7」鬼牌
    题意有\(n\)个球,\(m\)种颜色,\(i\)种颜色有\(a_i\)个球。每次随机选择两个球\(x\),\(y\)。使两个球的颜色都变为\(y\)的颜色。问最终只有一个颜色的球的期望步数。\(n\le10^9,m\le10^5\)。Sol显然的,考虑先枚举最终颜色,我们只关心当前有多少个最终颜色的球。......
  • 天天学编程Day7
    每日一道编程题155. 最小栈classMinStack{public://存储栈中元素及其出现次数的映射map<int,int>m;//存储实际栈元素的栈stack<int>s1;//记录当前栈中的最小元素intmin_num;MinStack(){//初始化时将最小元素设为......
  • DAY75WEB 攻防-验证码安全篇&接口滥用&识别插件&复用绕过&宏命令填入&滑块类
    知识点:1、验证码简单机制-验证码过于简单可爆破2、验证码重复使用-验证码验证机制可绕过3、验证码智能识别-验证码图形码被可识别4、验证码接口调用-验证码触发接口可枚举图片验证码-识别插件-登录爆破&接口枚举验证码识别绕过等技术适用于:口令存在爆破,接口枚举调用,任意......
  • Adobe IC 下载与快捷键使用【2017-2024】
    目录一、AdobeIC功能介绍1.1强大的图像编辑能力1.2丰富的画笔与图层管理工具1.3模板库与高效协作二、AdobeIC下载与安装2.1下载2.2安装三、AdobeIC快捷键使用3.1基本编辑快捷键3.2视图与导航快捷键3.3协作与批注快捷键一、AdobeIC功能介绍1.1......
  • E74 树形DP P4657 [CEOI2017] Chase
    视频链接:E74树形DPP4657[CEOI2017]Chase_哔哩哔哩_bilibili  P4657[CEOI2017]Chase-洛谷|计算机科学教育新生态(luogu.com.cn)//树形DPO(n*m)#include<bits/stdc++.h>#defineLLlonglongusingnamespacestd;constintN=100010,M=110;intidx,he......
  • 【并查集】【中间值范围】NOIP2017]奶酪
    https://ac.nowcoder.com/acm/contest/22904/1027开了ll还见祖宗注意x^2+y2算完之后先判断有没有超4r2的范围,没有的话再计算z^2,算是对longlong溢出的特判#include<bits/stdc++.h>typedeflonglongll;usingnamespacestd;classUnionFind{public:UnionFind(ll......
  • Adobe IC(InCopy)软件下载安装与系统要求【2017-2024】
    目录AdobeIC(InCopy)软件简介软件背景主要用途下载链接功能介绍高效协作丰富的编辑工具多种输出与自定义系统要求Windows系统macOS系统AdobeIC(InCopy)软件简介软件背景AdobeInCopy(简称IC)是Adobe公司开发的一款专业的文字处理软件,专为编辑和设计团队中的文本编......
  • 备战蓝桥杯JAVA B组Day7
    备战蓝桥杯JAVAB组Day7前言零基础小白备战蓝桥杯第七天,刷题内容为:洛谷题单【入门3】循环结构。P5722【深基4.例11】数列求和AC代码:importjava.util.Scanner;publicclassMain{publicstaticvoidmain(String[]args){Scannersc=newScanner(......
  • 历年CSP-J初赛真题解析 | 2017年CSP-J初赛完善程序(27-36)
    学习C++从娃娃抓起!记录下CSP-J备考学习过程中的题目,记录每一个瞬间。附上汇总贴:历年CSP-J初赛真题解析|汇总_热爱编程的通信人的博客-CSDN博客(快速幂)请完善下面的程序,该程序使用分治法求x......
  • 【IC】Adobe InCopy 图像编辑功能、win/mac下载与快捷键使用(2017-2024)
    目录一、AdobeIC功能介绍1.1核心功能1.2智能编辑与多平台支持二、AdobeIC下载2.1下载安装包2.2下载与安装步骤三、AdobeIC快捷键使用3.1文本编辑快捷键3.2视图与导航快捷键3.3协作与批注快捷键一、AdobeIC功能介绍1.1核心功能编辑与排版:AdobeI......