수열과 쿼리 0 [BOJ 13545]

수열과 쿼리 4와 수열과 쿼리 7과 같은 문제이다. 수열과 쿼리 4가 가장 기본형 문제이므로 수열과 쿼리 4를 풀면 이 문제도 자연스럽게 풀린다. 수열과 쿼리 4의 풀이 링크는 아래에 있다.

https://unorderedmap.tistory.com/33

수열과 쿼리 4 [BOJ 13546]

 

문제 요약

1과 -1로만 이루어진 길이 10만 이하의 수열 A에서 다음 쿼리를 수행한다.

i j : 구간 [i, j]에 포함되는 구간 중 구간합이 0인 가장 긴 구간의 길이 출력

 

사용 알고리즘

누적 합

Mo's Algorithm

 

풀이

수열 A에 누적합을 처리하면 수열과 쿼리 4와 같은 문제이다. 이 이상의 설명은 위에 있는 수열과 쿼리 4의 설명으로 대체한다.

 

코드

#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];
Query q[SIZE];
list<int> idx[2*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", &N);
    sqrtN=sqrt(N+1);
    A[1]=N;
    for (i=1; i<=N; i++) {
        scanf ("%d", &input[i]);
        A[i+1]=A[i]+input[i];
    }
    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]);
}

 

https://unorderedmap.tistory.com/13

1일 1수쿼 기록장