백준 19588 상품권 준비

https://www.acmicpc.net/problem/19588

19588번: 상품권 준비

xor은 누적합 테크닉 이용이 가능하다. 

a^b^a = b이므로

이 사실을 이문제 풀면서 처음 알았음. 

 

 

N,M의 제한이 10^5, 쿼리가 5*10^5 이므로 만약 쿼리마다 계산한다면 무조건 시간초과가 날 수 밖에 없다는 사실은 누구나 알 수 있다고 생각 

 

따라서 전처리를 어떻게 하느냐가 중요한 문제로 바뀌는데

 

문제에서 상위 b명은 제외되니깐 위에서 부터 어떻게 뽑는지 모양이 달라진다. 

그러니깐 

 

1

2

3

4

5

 

5명이 존재하고, 2명씩 그룹을 만들때 0명이 빠지면 (5,4),(3,2) 1명이 빠지면 (4,3), (2,1) 이런식으로 달라지게 되는데

이 모양은 총 M개 존재한다.

 

index 0부터 시작, 1부터 시작, ... M-1 부터 시작 

 

그리고 모든 M에 대해서 몇개를 그룹으로 이루어진건지 구해놓는다. 

이 개수는 총 N/M개이다. 

 

따라서 전처리에 O(N/M * M + N)의 시간복잡도가 필요하다.

 

쿼리문에서 받은 a,b로 잘 index계산해서 원하는 걸 출력하면 된다.

 

#include <bits/stdc++.h>
using namespace std;
#define MAX 200005
#define pii pair<int, int>
#define ll long long
#define pll pair<ll, ll>
#define INF 1e9
#define LINF 1e18
#define all(v) (v).begin(), (v).end()

vector<pll> num;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int T = 1;
    //cin >> T;
    while(T--) {
        ll N, M;
        cin >> N >> M;
        for(int i=0; i<N; i++){
            ll a, b;
            cin >> a >> b;
            num.emplace_back(a,b);
        }
        sort(all(num));
        vector<ll> sum(N+1);
        for(int i=1; i<=N; i++){
            sum[i] = sum[i-1]^num[i-1].second;
        }
        vector<vector<ll> > presum(N/M+1,vector<ll>(M,0));
        for(int i=0; i<M; i++){
            for(int j=1; j<=N/M; j++){
                presum[j][i] = (sum[i+j*M]^sum[i+j*M-M]) + presum[j-1][i];
            }
        }
        int Q;
        cin >> Q;
        for(int i=0; i<Q; i++){
            ll a, b;
            cin >> a >> b;
            ll k = N-b-a*M;
            k %= M;
            cout << presum[(N-b)/M][k] - presum[(N-b-a*M)/M][k] << '\n';
        }
    }
}