TIOJ-1927

2qbingxuan

2019-12-06

同步(Sync)

https://tioj.ck.tp.edu.tw/problems/1927

Description

在一個多人單向卷軸遊戲中，有$N \leq 10^5$個格子，每個格子都有一個不超過$10^9 + 6$的正整數，代表該格的狀況。
有時遊戲中的兩人會產生「同步」的現象。產生同步的條件是兩人所在的格子的數字$a,b$分別滿足
$$
(ab)^{\frac{p-1}{2}} \equiv 1 \pmod p
$$
其中$p = 10^9 + 7$。產生同步後，兩人會瞬移至下一格。如果在下一格又產生「同步」，則會繼續往下走，直到其中一人超出格子範圍(到了終點了)或者兩人不再同步。

Solution

對於$x \not\equiv 0 \pmod p$，$y = x^{\frac{p-1}{2}} \equiv \pm 1 \pmod p$
因為$y$是$1$的平方根(?)
然後$(ab)^{\frac{p-1}{2}} \equiv a^{(\frac{p-1}{2})} b^{(\frac{p-1}{2})}$
所以可先把所有值先$(p-1)/2$次方，一定會是$\pm 1$，接著他們同步的條件就可以簡化成$a = b$了

考慮到同步必須要是連續的性質，我們聯想到字串演算法中的後綴陣列，這題等價求兩個後綴的LCP，完全是SA的形狀XDD
SA + RMQ資結收工

注意查詢兩個同樣位置的情況，RMQ會查到空區間，不過我們知道這時候的答案顯然就是到尾巴的長度

AC code

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
//   __________________
//  | ________________ |
//  ||          ____  ||
//  ||   /\    |      ||
//  ||  /__\   |      ||
//  || /    \  |____  ||
//  ||________________||
//  |__________________|
//  \###################\
//   \###################\
//    \        ____       \
//     \_______\___\_______\
// An AC a day keeps the doctor away.

#pragma g++ optimize("Ofast")
#pragma loop_opt(on)
#include <bits/extc++.h>
#ifdef local
#define debug(x) (cerr<<#x<<" = "<<(x)<<'\n')
#else
#define debug(x) ((void)0)
#endif // local

using namespace std;
typedef int64_t ll;
constexpr ll N = 100025, INF = 1e18, MOD = 1000000007, K = 256, inf = 1e9;
ll modpow(ll e,ll p,ll m=MOD) {
    ll r=1;
    while(p) (p&1)&&(r=r*e%m), e=e*e%m, p>>=1;
    return r;
}

template<typename T>
struct SuffixArray {
    int sa[N],rk[N],tmp[N],lcp[N];
    void init(T v[],int n) {
        for(int i = 0; i < n; i++) rk[i] = v[i];
        iota(sa,sa+n,0);
        for(int L = 1; L < n; L*=2) {
            auto cmp = [&](int a,int b) {
                if(rk[a]!=rk[b]) return rk[a]<rk[b];
                int ra = (a+L<n ? rk[a+L] : -1);
                int rb = (b+L<n ? rk[b+L] : -1);
                return ra<rb;
            };
            sort(sa,sa+n,cmp);
            tmp[sa[0]] = 0;
            for(int i = 1; i < n; i++)
                tmp[sa[i]] = tmp[sa[i-1]] + cmp(sa[i-1],sa[i]);
            for(int i = 0; i < n; i++) rk[i] = tmp[i];
        }
        /*
        for(int i = 0; i < n; i++) {
            for(int j = sa[i]; j < n; j++) cout << v[j] << ' ';
            cout << '\n';
        }
        */
        lcp[n-1] = inf;
        for(int i = 0, h = 0; i < n; i++) {
            if(!rk[i]) continue;
            if(h > 0) --h;
            int j = sa[rk[i]-1];
            while(i+h<n && j+h<n && v[i+h]==v[j+h]) ++h;
            lcp[rk[i]-1] = h;
        }
        //for(int i = 0; i < n; i++) cout << lcp[i] << ' ';
    }
};
SuffixArray<int> SA;

struct SegmentTree {
    int mn[N<<1],n;
    void init(int v[],int _n) {
        n = _n;
        for(int i = 0; i < n; i++) mn[i+n] = v[i];
        for(int i = n-1; i > 0; i--) mn[i] = min(mn[i<<1], mn[i<<1|1]);
    }
    int query(int l,int r) {
        //cout << "qry: ";
        //for(int i = l; i < r; i++) cout << mn[i+n] << ' '; cout << '\n';
        int res = inf;
        for(l+=n,r+=n; l<r; l>>=1,r>>=1) {
            if(l&1) res = min(res, mn[l++]);
            if(r&1) res = min(res, mn[--r]);
        }
        return res;
    }
} RMQ;
int n,q,v[N];
signed main() {
    ios_base::sync_with_stdio(0), cin.tie(0);
    cin >> n >> q;
    for(int i = 0; i < n; i++) cin >> v[i];
    for(int i = 0; i < n; i++) v[i] = modpow(v[i], (MOD-1)/2);
    SA.init(v,n);
    RMQ.init(SA.lcp,n);
    for(int i = 0,a,b; i < q; i++) {
        cin >> a >> b;
        if(a == b) cout << n-a << '\n';
        else {
            int l = SA.rk[a], r = SA.rk[b];
            if(l > r) swap(l,r);
            cout << RMQ.query(l,r) << '\n';
        }
    }
}