首页 > 其他分享 >CF6E Exposition 题解 ST表+倍增

CF6E Exposition 题解 ST表+倍增

时间:2023-05-31 11:45:08浏览次数:40  
标签:cnt int 题解 ST CF6E maxn res Exposition 倍增

题目大意:

求所有极差不超过 \(k\) 的最长连续子序列。

解题思路:

先开一个 ST 表方便求解区间最大值和区间最小值。

然后基于倍增思想(详见 cal 函数)求极差不超过 \(k\) 的最长连续子序列。

示例程序:

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5;
int n, k, mx[maxn][18], mi[maxn][18], a[maxn], res[maxn];

int cal(int p) {
    int len = 1, x = a[p], y = a[p];
    for (int i = 17; i >= 0; i--)
        if (p + (1<<i) <= n && max(x, mx[p+1][i]) - min(y, mi[p+1][i]) <= k)
            len += 1<<i,
            x = max(x, mx[p+1][i]),
            y = min(y, mi[p+1][i]),
            p += 1<<i;
    return len;
}

int main() {
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; i++)
        scanf("%d", a+i), mx[i][0] = mi[i][0] = a[i];
    for (int j = 1; j < 18; j++)
        for (int i = 1; i+(1<<j)-1 <= n; i++)
            mx[i][j] = max(mx[i][j-1], mx[i+(1<<j-1)][j-1]),
            mi[i][j] = min(mi[i][j-1], mi[i+(1<<j-1)][j-1]);
    int x = 0, cnt = 0;
    for (int i = 1; i <= n; i++) {
        res[i] = cal(i);
        if (res[i] > x) x = res[i], cnt = 1;
        else if (res[i] == x) cnt++;
    }
    printf("%d %d\n", x, cnt);
    for (int i = 1; i <= n; i++)
        if (res[i] == x)
            printf("%d %d\n", i, i+x-1);
    return 0;
}

标签:cnt,int,题解,ST,CF6E,maxn,res,Exposition,倍增
From: https://www.cnblogs.com/quanjun/p/17445666.html

相关文章

  • Codeforces Round #548 (Div. 2) 题解
    题目链接http://codeforces.com/contest/1139 A.EvenSubstrings判断个位是否是奇数即可。#include<iostream>#include<set>#include<array>#include<vector>usingnamespacestd;typedeflonglongll;constintmx=1e5+10;lldp[mx][2];charstr[......
  • 牛客想开了大赛2 题解
    题目链接:https://ac.nowcoder.com/acm/contest/907#question A.【六】平面公式:(n*n+n)/2+1,n为直线数目B.【一】n的约数枚举质因子和每个质因子的个数,显然个数肯定从多到少。#include<bits/stdc++.h>typedeflonglongll;usingnamespacestd;constintmx=1e4+10;in......
  • Codeforces Round #594 (Div. 2) 题解
    题目链接:https://codeforces.com/contest/1248 A-IntegerPoints水题#include<bits/stdc++.h>usingnamespacestd;constintmx=1e5+5;typedeflonglongll;inta[mx],b[mx];intmain(){ intt; scanf("%d",&t); while(t--){ intn,m; scan......
  • Codeforces Round #599 (Div. 2) 题解
    题目链接:https://codeforces.com/contest/1243 A-MaximumSquare水题不说了#include<bits/stdc++.h>usingnamespacestd;constintmx=1e5+50;typedeflonglongll;intn;inta[mx];intmain(){ intt; scanf("%d",&t); while(t--){ scan......
  • 题解 AT_nikkei2019ex_e【コラッツ問題】
    啥玩意,诈骗题还能这么诈骗。\(f(X)\)就是角谷猜想(冰雹猜想)所需的步数。根据角谷猜想,定义函数\(g\):\[g(X)=\begin{cases}\frac{X}{2},&2\midX\\3X+1,&2\nmidX\end{cases}\]则显然有\(f(g(X))=f(X)-1\)。样例二已经给出了\(f(X)=1000\)的解\(X=1789997546303\),而\(P......
  • P9376 题解
    首先考虑怎么暴力。考虑把每个数进行\(B\)进制分解,然后我们惊奇的发现这两个操作就是把最低位去掉和往最低位后面插入一个数。然后我们顺藤摸瓜,把每个数的分解扔到Trie树上,我们发现我们要找到一个节点,使得所有单词节点到其的距离之和最短,答案就是这个最短距离。这里直接考......
  • CODE FESTIVAL 2016 qual B E 题解
    以下\(\Sigma\)为字符集。首先单次询问\(O(|\Sigma||S|)\)的暴力是显然的:建出trie树,然后每次把对应的字符串在上边扫,加上对应位置比它小的子树的大小。然后接下来有两种方法。正解首先在线大概是没什么前途的,考虑离线,建出trie树之后在上边dfs,处理挂在每个节点上的询......
  • CF1398E Two Types of Spells 题解 set
    题目链接:https://codeforces.com/problemset/problem/1398/E题目大意你有一个集合,初始为空。有两种类型的元素,一种是普通元素,一种是强化元素,两种元素都有一个数值。有\(n\)次操作,每次操作会往集合中加入一个元素或者删除一个元素。每次操作后,你都需要确定集合中元素的一个......
  • 第十四届蓝桥杯大赛青少组全国总决赛初级组C++C++题解
    第十四届蓝桥杯大赛青少组全国总决赛初级组\(C++\)题解第一题给定一个十进制正整数\(N(1≤N≤10^9)\),请从小到大输出\(1\)~\(N\)之间(含\(1\)和\(N\))所有满足以下要求的数:这个数转换为八进制后是一个回文数;这个数是一个平方数。例如:\(N=20\),在\(1\)~\(20\)之间满足要求......
  • 山东二轮省集题解合集
    山东二轮省集题解合集Day1A打表,发现答案是\(\prod\limits_{i=1}^n(2i-1)\)。证明可以考虑拿GF推。首先有dp,\(f(i,j)\)表示到第\(i\)个括号当前左括号减右括号的个数为\(j\),转移是简单的\(f(i,j)=f(i,j+1)+f(i,j-1)\times(j-1)\)把\(f(i,j)\)写成一个形式幂级......