简单的区间Interval

Description

题目大意是给出n个数,然后求满足条件的数量

Solvution

对于一个区间,设这个区间的最大值为,那么我们就可以考虑分治处理,对一个区间的处理显然不能同时枚举左端点和右端点,于是我们只考虑枚举一个端点。

如果,那么我们枚举右端点,否则枚举左端点,这样的话,如果一个位置被枚举到了一次,那么这个位置所在的区间就会缩小到原来的,这样就可以保证每一个位置至多被枚举到次。

我们将给出的式子变形
可得
因为左端点和最大值的位置确定,那么前缀和确定,于是问题就转化为在一段区间内找有多少个前缀和和最大值模k同余

然后对于这些询问我们可以离线做,给每一个左端点和右端点打一个标记,标记的值为最大值,最后扫一遍得到的前缀和数组,就可以得到最终的答案

所以最后复杂度是 的.

在枚举右端点的时候要注意,我们是在中找前缀和为,但是实际上如果要包括这个端点,实际上就是问是否同余,于是左端点就从变成了,这样就在左端点取值的范围上-1即可,同理,pos也要-1.

Code

#include <cstdio>
#include <ctype.h>
#include <cstdlib>

#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

#define putc(c) (*q++=c)
#define getc( ) (*p++)

char in[1 << 26] , *p;
char out[1 << 26] , *q;

inline void input() { fread(p = in,1,1 << 26,stdin) , q = out; }
inline void output() { fwrite(out,1,q - out,stdout); }

template<typename T>inline T read(T &f) {
    f = 0;
    int x = 1;
    char c = getc();
    while(!isdigit(c)) x = (c == '-' ? -1 : 1) , c = getc();
    while(isdigit(c)) f = (f << 1) + (f << 3) + c - '0' , c = getc();
    return f = f * x;
}

template<typename T>inline void write(T f) {
    if(f == 0){ putc('0') ; return; }
    if(f < 0) putc('-') , f = -f;
    static char str[20] , top = 0;
    while(f) str[++top] = f % 10 + '0' , f /= 10;
    while(top) putc(str[top--]);
}

#define writeln(f) write(f),putc('\n')
#define writesp(f) write(f),putc(' ')

#define LL long long

const int maxn = 300000 + 5;
const int maxk = 1000000 + 5;

int n , mod;
int A[maxn] , S[maxn];

vector<int> L[maxn] , R[maxn];

void update(int l , int r , int val){
    if(r == 0) return ;
    l = max(0 , l);
    L[l].push_back(val);
    R[r].push_back(val);
}

void interval(int l , int r){
    if(l >= r) return ;
    int pos , Max = 0;
    for(int i = l ; i <= r ; i++ )
        if(Max < A[i]) Max = A[i] , pos = i;
    Max %= mod;
    interval(l , pos - 1);
    interval(pos + 1 , r);
    int val;
    if(pos - l <= r - pos) { // 枚举左端点
        for(int i = l ; i < pos ; i++ ) {
            val = (S[i - 1] + Max) % mod;
            update(pos , r , val);
        }
        update(pos + 1 , r , (S[pos - 1] + Max) % mod);
    }
    else { // 枚举右端点
        for(int i = pos + 1; i <= r ; i++ ) {
            val = (S[i] - Max + mod) % mod;
            update(l - 1, pos - 1, val);
        }
        update(l - 1, pos - 2 , (S[pos] - Max + mod) % mod);
    }
}

int buc[maxk];
LL Ans;

void solve() {
    read(n) , read(mod);
    for(int i = 1 ; i <= n ; i++ ) S[i] = (read(A[i]) + S[i - 1]) % mod;
    interval(1 , n);
    for(int i = 0 ; i <= n ; i++) {
        for(int j = 0 ; j < L[i].size() ; j++ ) buc[ L[i][j] ]++;
        Ans += buc[ S[i] ];
        for(int j = 0 ; j < R[i].size() ; j++ ) buc[ R[i][j] ]--;
    }
    writeln(Ans);
}

int main() {
    input();
    solve();
    output();
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注