【树状数组】【P4113】[HEOI2012]采花

时间:2021-09-02 09:35:32

Description

给定一个长度为 \(n\) 的序列,有 \(m\) 次询问,每次询问一段区间,求区间中有多少个数出现次数超过 \(1\) 次

Limitation

\(n,~m~\leq~2~\times~10^6\)

Solution

好像和大众做法不大一样?

考虑对于每个位置,我们记一个 pre 和一个 post,代表他前面最后一个出现这个数的位置和他后面第一个出现这个数的位置。

考虑一个位置 \(x\) 对一个 \([l,~r]\) 的查询产生贡献当且仅当 \(pre_x~\geq~l\) 并且 \(post_x~>~r\)。

我们发现这个东西是可以树状数组维护的。

考虑统计一段区间内 pre 大于等于某个数的个数显然可以对 pre 开权值树状数组,然后按照左端点不升序排序,左端点左移的时候将对应位置的 pre 加入树状数组,一次查询的答案即为 \(BIT_{r}~-~BIT_{l - 1}\)。

现在考虑加入 \(post_x ~>~r\) 的限制。

我们发现当且仅当满足该条件的位置才对答案有贡献,于是我们只需要保证树状数组里只存有满足该条件的位置的 pre,就可以统计答案了。考虑按照右端点不升序排序,一开始先将最后一次出现的数字的 pre 加入到树状数组中,每次移动右端点的时候,将 post 为右端点所在位置的位置的 pre 加入树状数组即可(即将 \(post_x~=~R\) 的 \(x\) 的对应 \(per_x\) 加入树状数组)。由于大于右端点的部分的 pre 对答案同样没有贡献了,所以移动右端点的时候别忘了把右端点对应的 pre 在树状数组上删除。

Code

#include <cstdio>
#include <vector>
#include <algorithm>
#ifdef ONLINE_JUDGE
#define freopen(a, b, c)
#endif typedef long long int ll; namespace IPT {
const int L = 1000000;
char buf[L], *front=buf, *end=buf;
char GetChar() {
if (front == end) {
end = buf + fread(front = buf, 1, L, stdin);
if (front == end) return -1;
}
return *(front++);
}
} template <typename T>
inline void qr(T &x) {
char ch = IPT::GetChar(), lst = ' ';
while ((ch > '9') || (ch < '0')) lst = ch, ch=IPT::GetChar();
while ((ch >= '0') && (ch <= '9')) x = (x << 1) + (x << 3) + (ch ^ 48), ch = IPT::GetChar();
if (lst == '-') x = -x;
} namespace OPT {
char buf[120];
} template <typename T>
inline void qw(T x, const char aft, const bool pt) {
if (x < 0) {x = -x, putchar('-');}
int top=0;
do {OPT::buf[++top] = static_cast<char>(x % 10 + '0');} while (x /= 10);
while (top) putchar(OPT::buf[top--]);
if (pt) putchar(aft);
} const int maxn = 2000010; int n, c, m, dn;
int MU[maxn], oc[maxn], pos[maxn], pre[maxn], tree[maxn];
std::vector<int> vc[maxn]; struct Ask {
int l, r, id, ans; inline bool operator<(const Ask &_others) const {
return this->r > _others.r;
}
};
Ask ask[maxn];
bool cmp(const Ask&, const Ask&); int lowbit(int);
void update(int, int);
int query(int); int main() {
freopen("1.in", "r", stdin);
qr(n); qr(c); qr(m); dn = n + 1;
for (int i = 1; i <= n; ++i) {
qr(MU[i]); pre[i] = oc[MU[i]]; oc[MU[i]] = i;
}
for (int i = 1; i <= c; ++i) oc[i] = dn;
for (int i = n; i; --i) {
vc[pos[i] = oc[MU[i]]].push_back(i);
oc[MU[i]] = i;
}
for (int i = 1; i <= m; ++i) {
qr(ask[i].l); qr(ask[i].r); ask[i].id = i;
}
std::sort(ask + 1, ask + 1 + m);
for (auto i : vc[dn]) update(pre[i], 1);
for (int i = 1, R = n; i <= m; ++i) {
int l = ask[i].l, r = ask[i].r;
while (R > r) {
update(pre[R], -1);
for (auto j : vc[R]) update(pre[j], 1);
--R;
}
ask[i].ans = query(r) - query(l - 1);
}
std::sort(ask + 1, ask + 1 + m, cmp);
for (int i = 1; i <= m; ++i) {
qw(ask[i].ans, '\n', true);
}
return 0;
} inline bool cmp(const Ask &_a, const Ask &_b) {
return _a.id < _b.id;
} inline int lowbit(int x) {return x & -x;} void update(int x, int v) {
if (x == 0) return;
while (x <= dn) {
tree[x] += v;
x += lowbit(x);
}
} int query(int x) {
int _ret = 0;
while (x) {
_ret += tree[x];
x -= lowbit(x);
}
return _ret;
}

【树状数组】【P4113】[HEOI2012]采花的更多相关文章

  1. 洛谷P4113 &lbrack;HEOI2012&rsqb;采花

    题目描述 萧薰儿是古国的公主,平时的一大爱好是采花. 今天天气晴朗,阳光明媚,公主清晨便去了皇宫中新建的花园采花. 花园足够大,容纳了n朵花,花有c种颜色(用整数1-c表示),且花是排成一排的,以便于 ...

  2. P4113 &lbrack;HEOI2012&rsqb;采花 &lpar;莫队TLE&rpar;

    思路 update 11.2 树状数组AC 本题莫队过不去,会TLE ----------------------- 但也是个不错的莫队练手题 ------------------------ 毕竟C ...

  3. P4113 &lbrack;HEOI2012&rsqb;采花

    题目描述 萧薰儿是古国的公主,平时的一大爱好是采花. 今天天气晴朗,阳光明媚,公主清晨便去了皇宫中新建的花园采花. 花园足够大,容纳了n朵花,花有c种颜色(用整数1-c表示),且花是排成一排的,以便于 ...

  4. 【luogu P4113 &lbrack;HEOI2012&rsqb;采花】 假题解

    题目链接:https://www.luogu.org/problemnew/show/P4113 为什么要卡莫队!为什么加强的这么毒瘤! 莫队可以拿100分剩下三个点没治了 // luogu-judg ...

  5. LUOGU P4113 &lbrack;HEOI2012&rsqb;采花

    传送门 解题思路 莫队题卡莫队...莫队只能拿到100分,满分200.正解主席树??发个莫队100分代码. 代码 #include<iostream> #include<cstdio ...

  6. BZOJ&lowbar;2743&lowbar;&lbrack;HEOI2012&rsqb;采花&lowbar;离线&plus;树状数组

    BZOJ_2743_[HEOI2012]采花_离线+树状数组 Description 萧芸斓是Z国的公主,平时的一大爱好是采花.今天天气晴朗,阳光明媚,公主清晨便去了皇宫中新建的花园采花 .花园足够大 ...

  7. BZOJ 2743&colon; &lbrack;HEOI2012&rsqb;采花 离线树状数组

    2743: [HEOI2012]采花 题目连接: http://www.lydsy.com/JudgeOnline/problem.php?id=2743 Description 萧芸斓是Z国的公主, ...

  8. 【BZOJ2743】&lbrack;HEOI2012&rsqb;采花 离线&plus;树状数组

    [BZOJ2743][HEOI2012]采花 Description 萧芸斓是Z国的公主,平时的一大爱好是采花. 今天天气晴朗,阳光明媚,公主清晨便去了皇宫中新建的花园采花.花园足够大,容纳了n朵花, ...

  9. 【bzoj2743】&lbrack;HEOI2012&rsqb;采花 树状数组

    题目描述 萧芸斓是Z国的公主,平时的一大爱好是采花. 今天天气晴朗,阳光明媚,公主清晨便去了皇宫中新建的花园采花.花园足够大,容纳了n朵花,花有c种颜色(用整数1-c表示),且花是排成一排的,以便于公 ...

随机推荐

  1. 理解Cookie和Session机制&lpar;转&rpar;

    目录[-] Cookie机制 什么是Cookie 记录用户访问次数 Cookie的不可跨域名性 Unicode编码:保存中文 BASE64编码:保存二进制图片 设置Cookie的所有属性 Cookie ...

  2. Intellij修改archetype Plugin配置

    Maven archetype plugin为我们提供了方便的创建 project功能,Archtype指我们项目的骨架,作为项目的脚手架. 如fornt end的yo之类.我们能够通过简单的一行控制 ...

  3. 51nod 1413 权势二进制 背包dp

    1413 权势二进制 题目来源: CodeForces 基准时间限制:1 秒 空间限制:131072 KB  一个十进制整数被叫做权势二进制,当他的十进制表示的时候只由0或1组成.例如0,1,101, ...

  4. 经典线程同步 信号量Semaphore

    阅读本篇之前推荐阅读以下姊妹篇: <秒杀多线程第四篇一个经典的多线程同步问题> <秒杀多线程第五篇经典线程同步关键段CS> <秒杀多线程第六篇经典线程同步事件Event& ...

  5. leetcode 24

    链表操作的,要注意标记头结点和边界问题. 代码如下: ListNode *swapPairs(ListNode *head) { if(head==NULL||head->next==NULL) ...

  6. 表格实现hao123

    一.表格实现hao123用到的标签元素 1.[width][bordercolor][cellpadding][rules="none"隐藏表格内线框][border] 例如: & ...

  7. Spring&period;net架构示例&lpar;含Aop和Ioc&rpar;源码

    最近写了一个Spring.net的架构. 一.架构主图 架构图的数据流程走向是: UI层=>UILogic>=>Service>Business=>DataAccess ...

  8. iOS制作毛玻璃效果

    //添加一个图片 UIImageView *imageview = [[UIImageView alloc]init]; imageview.frame = CGRectMake(10, 100, 3 ...

  9. jvisualvm 连接 jstatd 远程监控 jvm 或 Visual GC提示&quot&semi;不受此JVM支持&OpenCurlyDoubleQuote;

    Visual GC提示"不受此JVM支持",可以使用此方法解决. 一.添加配置文件 jstatd.all.policy [root@localhost /]# cd /usr/lo ...

  10. redis(四)

    hash hash用于存储对象,对象的格式为键值对 命令 设置 设置单个属性 HSET key field value 设置多个属性 HMSET key field value [field valu ...