首页 > 其他 > 详细

美团codem 数列互质 - 莫队

时间:2018-09-14 17:58:27      阅读:169      评论:0      收藏:0      [点我收藏+]

题目描述

给出一个长度为 nnn 的数列 a1,a2,a3,...,an{ a_1 , a_2 , a_3 , ... , a_n }a?1??,a?2??,a?3??,...,a?n??,以及 mmm 组询问 (li,ri,ki)( l_i , r_i , k_i)(l?i??,r?i??,k?i??),求区间 [li,ri][ l_i , r_i ][l?i??,r?i??] 中有多少数在该区间中的出现次数与 kik_ik?i?? 互质。

输入格式

第一行,两个正整数 n,mn , mn,m。

第二行,nnn 个正整数 aia_ia?i?? 描述这个数列。

接下来 mmm 行,每行三个正整数 li,ri,kil_i , r_i , k_il?i??,r?i??,k?i??,描述一次询问。

输出格式

输出 mmm 行,即每次询问的答案。

样例

样例输入

10 5
1 1 1 1 1 2 2 2 2 2
4 7 2
4 7 3
4 8 2
4 8 3
3 8 3

样例输出

0
2
1
1
0

数据范围与提示

  • 1≤n,m≤5×1041\le n,m\le 5\times 10^41n,m5×10?4??
  • 1≤ai≤n1\le a_i\le n1a?i??n
  • 1≤li≤ri≤n1\le l_i\le r_i\le n1l?i??r?i??n
  • 1≤ki≤n1\le k_i\le n1k?i??n

 

思路分析 : 莫队基本题目,暴力维护的区间的元素有区间内不同元素的出现次数,同时再记录一下出现不同的次数有多少次,记录一下某个区间不同次数的种类,类似链表

    复杂度 :某个区间不同元素的次数种类最多有 根号n 种,总的复杂度就是 n*sqrt(n)*log(n)

    写的时候有个地方写错了,就是分块的排序的地方... 一直TLE

代码示例 :

using namespace std;
#define ll long long
const int maxn = 5e4+5;
const int mod = 1e9+7;
const double eps = 1e-9;
const double pi = acos(-1.0);
const int inf = 0x3f3f3f3f;

inline int read()
{
    int ret=0,c,f=1;
    for(c=getchar(); !(isdigit(c)||c==‘-‘); c=getchar());
    if(c==‘-‘) f=-1,c=getchar();
    for(; isdigit(c); c=getchar()) ret=ret*10+c-‘0‘;
    if(f<0) ret=-ret;
    return ret;
}

int n, m;
struct node
{
    int zu;
    int l, r, k, id;
    
    bool operator< (const node &v)const{
        if (zu == v.zu) return r < v.r;
        return l < v.l;
    }
}a[maxn];
int pre[maxn], cnt[maxn];
int num[maxn], time2[maxn<<2];
int all;
bool pt[maxn<<2];
int ans[maxn];

int gcd(int a, int b){
    return b==0?a:gcd(b, a%b);
}

inline void remove(int x){
    cnt[x]--;
    num[cnt[x]]++, num[cnt[x]+1]--;
    time2[all++] = cnt[x];
}

inline void add(int x){
    cnt[x]++;
    num[cnt[x]]++, num[cnt[x]-1]--;
    time2[all++] = cnt[x];
}

int main() {
    int l, r, k;
    
    cin >> n >> m;
    int unit = sqrt(n);
    for(int i = 1; i <= n; i++) pre[i] = read();
    for(int i = 1; i <= m; i++){
        l = read(), r = read(), k = read();
        //scanf("%d%d%d", &l, &r, &k);
        int f = (l-1)/unit+1;
        a[i] = {f, l, r, k, i}; 
    }
    sort(a+1, a+1+m);
    
    l = a[1].l, r = a[1].l-1; 
    all = 1; int sum = 0;
    for(int i = 1; i <= m; i++){ 
        while(l < a[i].l) remove(pre[l++]);
        while(r > a[i].r) remove(pre[r--]);
        while(l > a[i].l) add(pre[--l]);
        while(r < a[i].r) add(pre[++r]); 
        k = 1; sum = 0; 
        for(int j = 1; j < all; j++){
            if (!pt[time2[j]] && num[time2[j]] > 0){
                if (gcd(time2[j], a[i].k) == 1) {
                    sum += num[time2[j]];
                }
                time2[k++] = time2[j];
                pt[time2[j]] = true;
            }
        }
        all = k;
        ans[a[i].id] = sum;
        for(int j = 1; j < k; j++) pt[time2[j]] = false;
    }
    for(int i = 1; i <= m; i++) printf("%d\n", ans[i]);
    return 0;
}

 

美团codem 数列互质 - 莫队

原文:https://www.cnblogs.com/ccut-ry/p/9648076.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!