CF543E Listening to Music

时间:2022-12-31 15:25:30

题面

空间只有$64\text{MB}$!!!

题解

(据说正解是毒瘤分块套分块)

按照权值从大到小排序,对所有能够覆盖到它的区间的左端点打个标记

按照值域建一棵主席树就可以了

区间查询最大值,用$m$减去它即可

如何卡空间???

  1. 用位域将主席树的节点信息压到一个unsigned long long
  2. 将叶节点改成一个值,节省空间。(但是还是要开40倍)
  3. 永久化的标记和值压在一起。

最后以大约$63\text{MB}$的空间卡了过去。

代码

#include<cstdio>
#include<cstring>
#include<cctype>
#include<algorithm>
#define RG register
#define file(x) freopen(#x".in", "r", stdin);freopen(#x".out", "w", stdout);
#define clear(x, y) memset(x, y, sizeof(x)) inline int read()
{
int data = 0, w = 1; char ch = getchar();
while(ch != '-' && (!isdigit(ch))) ch = getchar();
if(ch == '-') w = -1, ch = getchar();
while(isdigit(ch)) data = data * 10 + (ch ^ 48), ch = getchar();
return data * w;
} const int maxn(2e5 + 10), INT_MAX(1e9);
#define lmax (l == mid ? int(t[rt].lson) : int(t[t[rt].lson].max))
#define rmax (mid + 1 == r ? int(t[rt].rson) : int(t[t[rt].rson].max)) struct node { unsigned long long max : 18, lson : 23, rson : 23; } t[maxn * 40];
int cur, root[maxn], n, m, Q;
std::pair<int, int> a[maxn]; int Insert(int p, int l, int r, int ql, int qr)
{
if(l == r) return p + 1;
int rt = ++cur; t[rt] = t[p];
if(ql <= l && r <= qr) return ++t[rt].max, rt;
int mid = (l + r) >> 1, tag = t[rt].max - std::max(lmax, rmax);
if(ql <= mid) t[rt].lson = Insert(t[p].lson, l, mid, ql, qr);
if(qr > mid) t[rt].rson = Insert(t[p].rson, mid + 1, r, ql, qr);
t[rt].max = std::max(lmax, rmax) + tag; return rt;
} int query(int rt, int l, int r, int ql, int qr)
{
if(l == r) return rt;
if(ql <= l && r <= qr) return t[rt].max;
int mid = (l + r) >> 1, ans = 0, tag = t[rt].max - std::max(lmax, rmax);
if(ql <= mid) ans = std::max(ans, query(t[rt].lson, l, mid, ql, qr));
if(qr > mid) ans = std::max(ans, query(t[rt].rson, mid + 1, r, ql, qr));
return ans + tag;
} int main()
{
#ifndef ONLINE_JUDGE
file(cpp);
#endif
n = read(), m = read();
for(RG int i = 1; i <= n; i++) a[i] = std::make_pair(-read(), i);
std::sort(a + 1, a + n + 1);
for(RG int i = 1; i <= n; i++)
{
int ql = std::max(1, a[i].second - m + 1);
int qr = std::min(a[i].second, n - m + 1);
root[i] = Insert(root[i - 1], 1, n - m + 1, ql, qr);
}
Q = read(); int ans = 0;
while(Q--)
{
int l = read(), r = read(), x = read() ^ ans;
int id = std::upper_bound(a + 1, a + n + 1,
std::make_pair(-x, INT_MAX)) - a - 1;
printf("%d\n", ans = m - query(root[id], 1, n - m + 1, l, r));
}
return 0;
}

CF543E Listening to Music的更多相关文章

  1. 【CF543E】Listening to Music

    [CF543E]Listening to Music 题面 洛谷 题目大意 给你一个长度为\(n\)序列\(a_i\),和一个常数\(m\),定义一个函数\(f(l,x)\)为\([l,l+m-1]\ ...

  2. &lbrack;WPF系列&rsqb;基础 Listening to Dependency Property change notifications of a given Element

    I want to share this great post from Anoop that shows a easy way to add a notification system to dep ...

  3. &lbrack;BEC&rsqb;&lbrack;hujiang&rsqb; Lesson03 Unit1&colon;Working life ---Grammar &amp&semi; Listening &amp&semi; Vocabulary

    3 Working life p8 Grammar Gerund and infinitive(动名词和不定式) 一般而言:        1 动词后面接动名词还是不定式没有特定规则,主要取决于语言习 ...

  4. 错误信息&colon;A TCP error &lpar;10013&colon; 以一种访问权限不允许的方式做了一个访问套接字的尝试。&rpar; occurred while listening on IP Endpoint&equals;192&period;168&period;1&period;18&colon;8002&period;

    百度之后,知道这个原因是端口已经被其他进程打开了 使用cmd命令,查看8002端口被哪一个程序占用了 C:\Windows\System32>netstat -ano | find " ...

  5. 启动redis出现Creating Server TCP listening socket &ast;&colon;6379&colon; bind&colon; No such file or directory

    E:\redis>redis-server.exe redis.windows.conf [8564] 10 Oct 20:00:36.745 # Creating Server TCP lis ...

  6. ERROR&colon; unable to bind listening socket for address ’127

    ERROR: unable to bind listening socket for address '127.0.0.1:9000′ 解决办法: killall php-fpm 然后重启即可. 我的 ...

  7. creating server tcp listening socket 127&period;0&period;0&period;1&colon;6379&colon; bind No error

    参考链接:https://blog.csdn.net/n_fly/article/details/52692480 1.window10环境下面安装的redis,之前安装好弄了一下,过了好几天,再次使 ...

  8. 报错处理——&num; Creating Server TCP listening socket &ast;&colon;6379&colon; bind&colon; Address already in use

    在启动redis时报错 # Creating Server TCP listening socket *:6379: bind: Address already in use 错误原因 6379地址已 ...

  9. redis启动出现错误creating server tcp listening socket 127&period;0&period;0&period;1&colon;6379&colon; bind No error

    creating server tcp listening socket 127.0.0.1:6379: bind No error 的解决方案如下按顺序输入如下命令就可以连接成功 1. redis- ...

随机推荐

  1. (十一)WebGIS中要素(Feature)的设计

    文章版权由作者李晓晖和博客园共有,若转载请于明显处标明出处:http://www.cnblogs.com/naaoveGIS/. 1.前言 在GIS中元素一般分为点元素,线元素,面元素以及symbol ...

  2. android 开发进阶 自定义控件-仿ios自动清除控件

    先上图: 开发中经常需要自定义view控件或者组合控件,某些控件可能需要一些额外的配置.比如自定义一个标题栏,你可能需要根据不同尺寸的手机定制不同长度的标题栏,或者更常见的你需要配置标题栏的背景,这时 ...

  3. java匿名内部类练习

    interface Inter { void method(); } class Test { //补足代码.通过匿名内部类. /* static class Inner implements Int ...

  4. 安卓应用开发用户体验之禁止EditText自动获取焦点

    一.问题描述: 在安卓应用开发时,经常会在同一个页面有许多不同的控件,在用户操作时,如何正确的在这些控件之间来回切换是良好用户体验的重要问题.可能会碰到如下问题:在点击页面内某控件时(假设控件为Spi ...

  5. mysql字符集问题 错误代码: 1267 Illegal mix of collations &lpar;utf8&lowbar;general&lowbar;ci&comma;IMPLICIT&rpar; and &lpar;utf8&lowbar;croatian&lowbar;ci&comma;IMPLICIT&rpar; for operation &&num;39&semi;&equals;&&num;39&semi;

    一般是多表或跨库表查询导致出现的问题,其原因是两张表的字符集不一样导致的,那为什么两张表的字符集会不一样?这是由于架构师或者开发人员在建表的时候不小心选错字符集的原因导致的. 那好我们把两张表(或两个 ...

  6. SPOJ 694 DISUBSTR - Distinct Substrings

    思路 求本质不同的子串个数,总共重叠的子串个数就是height数组的和 总子串个数-height数组的和即可 代码 #include <cstdio> #include <algor ...

  7. &lbrack;UGUI&rsqb;图文混排&lpar;一&rpar;:标签制定和解析

    参考链接: https://github.com/SylarLi/RichText/tree/master/Assets/Scripts 正则表达式: https://blog.csdn.net/ly ...

  8. 基元线程同步构造 AutoResetEvent和ManualResetEvent 线程同步

    在.Net多线程编程中,AutoResetEvent和ManualResetEvent这两个类经常用到, 他们的用法很类似,但也有区别.ManualResetEvent和AutoResetEvent都 ...

  9. MFC【17-3】线程和线程同步化

    17.3小知识点 17.3.1消息泵 编写一个应用程序,让它响应某菜单命令,画几千个椭圆. void CMFC线程View::OnStartDrawing(void) { m_bQuit=FALSE; ...

  10. MongoDb 本机删除密码的方法

    Terminal Inflection LINUX ESOTERICA, FIXES AND RANTS About Errors Resolved Linux Recommended Books W ...