UOJ#213——【UNR #1】争夺圣杯

时间:2022-08-30 23:35:55

1、题意:给一个序列,枚举长度x,然后在这个序列中所有长度为x的区间,我们求出这些区间的最大值之和并取模,最后将所有的异或起来就好啦

2、分析:听说好多人写的 ,特来写一发 的算法骗访问量

话说这个东西,我们对于每一个点,设这个点的值是,我们可以求出他影响的所有区间,这个用单调栈解决即可,也就是说求出左边和右边第一个比这个点大的值的位置,设左边那个哪个位置是,右边那个位置是,那么我们就能得到这些区间啦,然后我们就可以随便写写就A了 ,这明显是不能AC的,那我们考虑一个点对于每个长度的贡献,考虑这样的一个点,令,我们处理时方便,打出表来(雾),其实能看出来,我们的这个贡献变成了一个分段函数:

①当时,;

②当时,;

③当时,。

那么我们分别来计算这三个函数对答案的贡献。

①:这个我们可以找出一个长度和一个长度的区别,那么所有 长度有的贡献的位置,在 这个位置也一定拥有,只不过差了一个(根据那个函数是个等差数列能得出),但是当时,这个位置就对于 有贡献,而对 没有贡献,所以我对于所有的贡献,我在l这个位置加上一个小标记,标记是那个,那么我从后向前递推,也就是说,其中 表示这个点累计的标记和

②:这个是最水的一个,我们差分一下,然后求一下前缀和就好了QAQ。

③:这个貌似是最复杂的一个,还是打标记这种东西,我们发现这个分段函数单调递减,那么我们在递减开始的 这个位置打一个标记,就是加上,也是差分,那么我们每次都要在一个位置减掉一个,因为贡献是单调递减的,那么我们还要维护这个差分的数组,另外这个递减最后变成0后就不会再递减了,所以还要开一个差分数组,这段说起来很繁琐,具体看看代码吧

最后友情提示,那个单调栈的判断一定要左边寻找比他大,右边寻找大于等于它的,这样相等的情况才能包括进去

解决啦,撒花!

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
#define M 1000010
#define LL long long
#define MOD 998244353

inline int read(){
    char ch = getchar(); int x = 0, f = 1;
    while(ch < '0' || ch > '9'){
        if(ch == '-') f = -1;
        ch = getchar();
    }
    while('0' <= ch && ch <= '9'){
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}

int a[M];
int ll[M];
int rr[M];
int z[M], tot;
LL ans[M], beta[M], lazy[M], plus[M], vfk[M];
LL cf[M];

int main(){
    int n = read();
    for(int i = 1; i <= n; i ++) a[i] = read();
    for(int i = 1; i <= n; i ++){
        while(tot > 0 && a[z[tot]] <= a[i]) tot --;
        ll[i] = z[tot]; z[++ tot] = i;
    }
    tot = 0; z[0] = n + 1;
    for(int i = n; i >= 1; i --){
        while(tot > 0 && a[z[tot]] < a[i]) tot --;
        rr[i] = z[tot]; z[++ tot] = i;
    }
    for(int i = 1; i <= n; i ++){
        int l = i - ll[i] - 1;
        int r = rr[i] - i - 1;
        if(l > r) swap(l, r);
        if(l != 0){
            LL w = min(l, r);
            lazy[w] += (LL)w * (LL)a[i];
            beta[r + 2] += (LL)w * (LL)a[i];
            //puts("fuck");
            plus[r + 2] += a[i];
            vfk[r + 2 + l] += a[i];
        }
        cf[l + 1] += (LL)(l + 1) * (LL)a[i];
        cf[r + 2] -= (LL)(l + 1) * (LL)a[i];
    }
    for(int i = n + 1; i > 1; i --){
        ans[i - 1] = ans[i] / (LL)(i) * (LL)(i - 1) + lazy[i - 1];
    }
    LL sum = 0ll, divt = 0ll;
    for(int i = 1; i <= n; i ++){
        sum += beta[i] - divt;
        divt += plus[i];
        divt -= vfk[i];
        ans[i] += sum;
    }
    sum = 0ll;
    for(int i = 1; i <= n; i ++){
        sum += cf[i];
        ans[i] += sum;
    }
    for(int i = 1; i <= n; i ++) ans[i] %= MOD;
    LL res = 0ll;
    for(int i = 1; i <= n; i ++){
        res ^= ans[i];
    }
    printf("%lld\n", res);
    return 0;
}

UOJ#213——【UNR #1】争夺圣杯的更多相关文章

  1. 【uoj&num;213】&lbrack;UNR &num;1&rsqb;争夺圣杯 单调栈&plus;差分

    题目描述 给出一个长度为 $n$ 的序列,对于 $1\sim n$ 的每一个数 $i$ ,求这个序列所有长度为 $i$ 的子区间的最大值之和,输出每一个 $i$ 的答案模 $998244353$ 后异 ...

  2. &lbrack;UOJ213&rsqb;&lbrack;UNR &num;1&rsqb;争夺圣杯

    uoj description 一个长为\(n\)的序列,给定一个参数\(m\),求所有长度为\(m\)的区间的最大值之和. 对于所有的\(m\in[1,n]\)你都需要分别求出答案然后异或起来. \ ...

  3. uoj&num;213&period; 【UNR &num;1】争夺圣杯

    http://uoj.ac/problem/209 单调栈求出每个位置x左边第一个大于它的位置L[x]和右第一个不小于它的位置R[x],于是矩形L[x]<=l<=x<=r<=R ...

  4. uoj&num;213&period; 【UNR &num;1】争夺圣杯(单调栈)

    传送门 我们枚举每一个元素,用单调栈做两遍计算出它左边第一个大于它的位置\(l[i]\)和右边第一个大于它的位置\(r[i]\),那么一个区间以它为最大值就意味着这个区间的左端点在\([l[i]+1, ...

  5. 【UOJ UNR &num;1】争夺圣杯

    来自FallDream的博客,未经允许,请勿转载,谢谢. 传送门 考虑直接对每个数字,统计它会产生的贡献. 单调栈求出每个数字左边第一个大等于他的数,右边第一个大于他的 (注意只能有一边取等) 假设左 ...

  6. A&period; 【UNR &num;1】争夺圣杯

    题解: 一道比较水的题目 按照最一般的思路离散化后枚举最大值 然后考虑最大值的贡献 会发现需要分类讨论一下 发现对一段k的影响是等差数列 所以可以用线段树维护差分数组

  7. uoj213 【UNR &num;1】争夺圣杯

    题目 设\(f_i\)表示所有长度为\(i\)的区间的最大值的和,求\(\bigoplus \sum_{i=1}^nf_i\) 不难发现随机数据非常好做 由于一个随机序列的前缀最大值期望只会变化\(\ ...

  8. UOJ&period;311&period;&lbrack;UNR&num;2&rsqb;积劳成疾&lpar;DP&rpar;

    UOJ 序列中的每个位置是等价的.直接令\(f[i][j]\)表示,\(i\)个数的序列,最大值不超过\(j\)的所有序列每个长为\(k\)的子区间最大值的乘积的和. 由\(j-1\)转移到\(j\) ...

  9. uoj【UNR &num;3】To Do Tree 【贪心】

    题目链接 uojUNR3B 题解 如果不输出方案,是有一个经典的三分做法的 但是要输出方案也是可以贪心的 设\(d[i]\)为\(i\)节点到最深的儿子的距离 贪心选择\(d[i]\)大的即可 #in ...

随机推荐

  1. 【转载】【树形DP】【数学期望】Codeforces Round &num;362 &lpar;Div&period; 2&rpar; D&period;Puzzles

    期望计算的套路: 1.定义:算出所有测试值的和,除以测试次数. 2.定义:算出所有值出现的概率与其乘积之和. 3.用前一步的期望,加上两者的期望距离,递推出来. 题意: 一个树,dfs遍历子树的顺序是 ...

  2. vb和php 基于socket通信

    php代码(页面代码非cmd命令脚本) <?php $server = '127.0.0.1'; $port = 8888; $socket = socket_create(AF_INET, S ...

  3. 读《编写高质量代码-Web前端开发修炼之道》笔记

    第一章 1.Web标准由一系列标准组合而成,核心理念是将网页的结构,样式和行为分离,所以分为三大部分:结构标准,样式标准和行为标准.结构标准包括XML标准,XHTML标准,HTML标准:样式标准指CS ...

  4. 将 Qt 5&period;6 集成至 VS2015

    摘要: 由于VS2015不再支持addin,所以要用其他手段. 这里给出64位系统下的安装步骤,32位类似. 一.安装VS2015 过程略.值得注意的是要选择需要安装的内容,既然要用Qt,那么C++相 ...

  5. bzoj 2618 2618&colon; &lbrack;Cqoi2006&rsqb;凸多边形(半平面交)

    2618: [Cqoi2006]凸多边形 Time Limit: 5 Sec  Memory Limit: 128 MBSubmit: 656  Solved: 340[Submit][Status] ...

  6. &lbrack;JAVA&rsqb; - Java OutOfMemoryError分类

    Java OutOfMemoryError一般常遇到的分为两类,分别提示: "Java heap space" 和 "PermGen space",前面的是指j ...

  7. Vue&plus;koa2开发一款全栈小程序&lpar;8&period;图书列表页)

    1.图书列表页获取数据 1.在server/routes/index.js中新增路由 router.get('/booklist',controllers.booklist) 2.在server/co ...

  8. Chameleon

    # -*- coding: utf-8 -*- """ Created on Tue Dec 18 09:55:16 2018 @author: Mark,LI &quo ...

  9. H5页面开发笔记(react技术栈)

    1.子组件接收父组件的参数,要在子组件的componentDidMount函数中更改当前组件的state,若写在componentWillMount函数中,则会导致初始化界面UI的时候不能得到预期的效 ...

  10. spring cloud要点简介及常用组件

    spring cloud基于spring boot spring cloud是通过包装其他技术框架实现的,例如OSS组件,实现了一套通过基于注解.java配置和基于模板开发的微服务框架. spring ...