수열과 쿼리 7 [BOJ 13550]

수열과 쿼리 0과 수열과 쿼리 4와 같은 문제이다. 정확히는 수열과 쿼리 0에서 mod K만 씌우면 된다. 수열과 쿼리 0의 풀이 링크로 이 문제의 풀이를 대체한다.

https://unorderedmap.tistory.com/34

수열과 쿼리 0 [BOJ 13545]

 

코드

#include <bits/stdc++.h>
#define SIZE 100003
typedef long long ll;
using namespace std;
struct Query
{
    int id, s, e;
};
int A[SIZE], c[SIZE], sqrtN, ans[SIZE], res, input[SIZE], K;
Query q[SIZE];
list<int> idx[10*SIZE];
bool comp(Query x, Query y)
{
    if (x.s/sqrtN==y.s/sqrtN) {
        if (x.e==y.e) return x.s<y.s;
        return x.e<y.e;
    }
    return x.s/sqrtN<y.s/sqrtN;
}
void mo_radd(int x)
{
    int l, r;
    if (idx[A[x]].size()>=2) {
        l=idx[A[x]].front(), r=idx[A[x]].back();
        c[r-l]--;
    }
    idx[A[x]].push_back(x);
    if (idx[A[x]].size()>=2) {
        l=idx[A[x]].front(), r=idx[A[x]].back();
        c[r-l]++;
        res=max(res, r-l);
    }
}
void mo_rdis(int x)
{
    int l, r;
    if (idx[A[x]].size()>=2) {
        l=idx[A[x]].front(), r=idx[A[x]].back();
        c[r-l]--;
    }
    idx[A[x]].pop_back();
    if (idx[A[x]].size()>=2) {
        l=idx[A[x]].front(), r=idx[A[x]].back();
        c[r-l]++;
        res=max(res, r-l);
    }
}
void mo_ladd(int x)
{
    int l, r;
    if (idx[A[x]].size()>=2) {
        l=idx[A[x]].front(), r=idx[A[x]].back();
        c[r-l]--;
    }
    idx[A[x]].push_front(x);
    if (idx[A[x]].size()>=2) {
        l=idx[A[x]].front(), r=idx[A[x]].back();
        c[r-l]++;
        res=max(res, r-l);
    }
}
void mo_ldis(int x)
{
    int l, r;
    if (idx[A[x]].size()>=2) {
        l=idx[A[x]].front(), r=idx[A[x]].back();
        c[r-l]--;
    }
    idx[A[x]].pop_front();
    if (idx[A[x]].size()>=2) {
        l=idx[A[x]].front(), r=idx[A[x]].back();
        c[r-l]++;
        res=max(res, r-l);
    }
}
int main()
{
    int N, M, i;
    scanf ("%d %d", &N, &K);
    sqrtN=sqrt(N+1);
    for (i=1; i<=N; i++) {
        scanf ("%d", &input[i]);
        A[i+1]=(A[i]+input[i]%K)%K;
    }
    scanf ("%d", &M);
    for (i=0; i<M; i++) {
        scanf ("%d %d", &q[i].s, &q[i].e);
        q[i].id=i, q[i].e++;
    }
    sort(q, q+M, comp);
    int s=q[0].s, e=q[0].e;
    for (i=s; i<=e; i++) mo_radd(i);
    ans[q[0].id]=res, c[0]=N+2;
    for (i=1; i<M; i++) {
        while (s>q[i].s) mo_ladd(--s);
        while (e<q[i].e) mo_radd(++e);
        while (s<q[i].s) mo_ldis(s++);
        while (e>q[i].e) mo_rdis(e--);
        while (c[res]==0) res--;
        ans[q[i].id]=res;
    }
    for (i=0; i<M; i++) printf("%d\n", ans[i]);
}