公主的朋友

Description

Problem

由于\(Wulala\)在上个问题中的精彩表现，公主认为\(Wulala\)是一个很棒的人，就把\(Wulala\)留在 了\(X\)国。这时正好公主的一位传教士朋友来拜访公主，于是想找\(wulala\)帮忙。

\(X\)国如同一条直线，其中有\(n\)个城市,从东向西分别编号为\(1\)到\(n\)。而他的国家中有\(m\)种宗教， 每个城市一定会有一种信仰的宗教。 有时候有些城市为了获得更多的认可，会派出信仰本城市宗教的传教士前往其他国家。

\(X\)国的传教士都十分厉害，只要是他途经的地方都会改信他所传播的宗教。 传教士们在路上碰到自己宗教的城市自然就不用传教了，所以每 一个传教士在旅行前都会计算自己可以在多少城市停下来(不包括起始的城市)。

而传教士们都是文科僧，数学是很差的，所以他希望\(Wulala\)能帮他计算。可\(Wulala\)数学也不好，但他又不想在公主面前丢脸，你能帮帮他吗？

Input Data

第一行两个整数\(n\)，\(m\)；
第二行\(n\)个整数第\(i\)个整数代表第ii个城市信仰的宗教；
第三行一个整数 \(T\) 代表传教士的个数；
接下来 \(T\) 行每行两个整数 \(x\)，\(y\)代表 \(x\) 城向 \(y\) 城派遣了一个传教士(保证 \(x<y\))

Output Data

输出\(T\)行，第\(i\)行代表第\(i\)个传教士询问的答案

Input / Output Sample

2 2
1 2
2
1 2
1 2

0
1

Data Limit

对于 30%的数据 \(n \le 100000, m \le 10, T \le100\);
对于 60%的数据 \(n \le 100000, m \le 10, T \le 100000\);
对于 100%的数据 \(n \le 100000, m \le 300, T \le 100000\)。

Problem Source

湖南师大附中模拟赛

这又和\(数列分块入门8\)蜜汁相似QAQ

\(^双_经\) $^倍_验 $泛滥成灾啊

这里也不多提，参照\(数列分块入门8\)

代码

#include<bits/stdc++.h>
using namespace std;
#define MAXN 100005

int n, m, d, T;
int a[MAXN], b[MAXN], f[500];
bool v[500];

int FF( int x ){
    return v[b[x]] ? f[b[x]] : a[x];
}

int fun( int l, int r, int c ){
    int ans(0);
    for ( int i = l; i <= r && i <= n; ++i ) ans += FF(i) == c, a[i] = c;
    return ans;
}

int Get( int l, int r, int c ){
    int ans(0);
    if ( b[l] == b[r] ){
        if ( v[b[l]] && f[b[l]] == c ) return r - l + 1;
        
        if ( v[b[l]] ){
            fun( ( b[l] - 1 ) * d + 1, l - 1, f[b[l]] );
            fun( r + 1, b[l] * d, f[b[l]] );
        }
        ans = fun( l, r, c );
        v[b[l]] = 0;
        return ans;
    }
    
    if ( v[b[l]] ) fun( ( b[l] - 1 ) * d + 1, l - 1, f[b[l]] );
    ans += fun( l, b[l] * d, c );
    v[b[l]] = 0;
    
    
    if ( v[b[r]] ) fun( r + 1, min( b[r] * d, n ), f[b[r]] );
    ans += fun( ( b[r] - 1 ) * d + 1, r, c );
    v[b[r]] = 0;
    
    for ( int i = b[l] + 1; i <= b[r] - 1; ++i ){
        if ( !v[i] ){
            for ( int j = ( i - 1 ) * d + 1; b[j] == i; ++j ) ans += a[j] == c, a[j] = c;
            v[i] = 1; f[i] = c;
        } else{
            if ( f[i] == c ) ans += d;
            else f[i] = c;
        }
    }
    return ans;
}

int main(){
    scanf( "%d%d", &n, &m );
    d = (int)sqrt(n);
    for ( int i = 1; i <= n; ++i ){
        scanf( "%d", &a[i] );
        b[i] = ( i - 1 ) / d + 1;
    }
    scanf( "%d", &T );
    while ( T-- ){
        int l, r;
        scanf( "%d%d", &l ,&r );
        printf( "%d\n", Get( l, r, FF(l) ) - 1 );
    }
    return 0;
}

数列分块系列目录

数列分块入门1

数列分块入门2

数列分块入门3

数列分块入门4

数列分块入门5

数列分块入门6

数列分块入门7

数列分块入门8

数列分块入门9

蒲公英

公主的朋友 <-