C++14(g++5.4) 解法, 执行用时: 4410ms, 内存消耗: 24880K, 提交时间: 2018-08-19 21:11:23
#include <iostream>
#include <cmath>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cassert>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
int seed;
int getrand(){
return seed=(1ll*seed*100000005+20150609)%998244353;
}
const int N=110000,M=40;
int n,m,x[N];
struct tree{
int l,r,size;
}t[N*20];
int len,root[N],a[N],ra[N];
__int128 w[N];
int insert(int k1,int k2,int k3,int k4){
int now=++len; t[now]=t[k1]; t[now].size+=1;
int mid=(k2+k3)>>1; if (k2==k3) return now;
if (mid>=k4) t[now].l=insert(t[k1].l,k2,mid,k4);
else t[now].r=insert(t[k1].r,mid+1,k3,k4);
return now;
}
pair<int,__int128> getall(int k1,int k2,int k3,int k4,int K){
if (k3==k4){
return mp(a[k3],w[a[k3]]);
}
int now=t[t[k1].l].size-t[t[k2].l].size,mid=(k3+k4)>>1;
if (now>=K) return getall(t[k1].l,t[k2].l,k3,mid,K);
else return getall(t[k1].r,t[k2].r,mid+1,k4,K-now);
}
__int128 get(int l,int len){
return w[l]>>(M-len);
}
__int128 get(int s,int l,int r,int now){
int k1=r-s+1,k2=now-k1;
return (get(s,k1)<<k2)+get(l,k2);
}
int b[N];
void mysort(int k1,int k2,int l,int r,int d){
if (k1>=k2) return;
if (d==r-l+1){
sort(b+k1,b+k2+1); return;
}
int M=k1-1;
for (int i=k1;i<=k2;i++){
int now=(b[i]-l+d)%(r-l+1)+l;
if (x[now]==0){
M++; swap(b[M],b[i]);
}
}
mysort(k1,M,l,r,d+1);
mysort(M+1,k2,l,r,d+1);
}
struct bwtgen{
int l,r,mid,lim,nowK,s;
vector<pair<int,__int128> >A;
bwtgen(int _l,int _r){
l=_l; r=_r; mid=r-M+1;
if (mid>=l) lim=t[root[mid]].size-t[root[l-1]].size;
else lim=0;
int len=0;
for (int i=max(l,mid+1);i<=r;i++) b[++len]=i;
mysort(1,len,l,r,0); A.clear();
for (int i=1;i<=len;i++) A.push_back(mp(b[i],get(b[i],l,r,min(r-l+1,M))));
for (int i=1;i<(int)(A.size());i++) assert(A[i-1].se<=A[i].se);
nowK=1; s=0;
}
int getnext(){
pair<int,__int128> w1,w2,ans;
if (s==(int)(A.size())) w1=mp(-1,0); else w1=A[s];
if (nowK>lim) w2=mp(-1,0); else w2=getall(root[mid],root[l-1],1,n,nowK);
if (w1.fi==-1&&w2.fi==-1) return -1;
if (w1.fi==-1){
nowK++; ans=w2;
} else if (w2.fi==-1){
s++; ans=w1;
} else if (w1.se<w2.se||(w1.se==w2.se&&w1.fi<w2.fi)){
s++; ans=w1;
} else nowK++,ans=w2;
if (ans.fi==l) return x[r]; else return x[ans.fi-1];
}
};
int ma=0;
int check(bwtgen k1,bwtgen k2){
int t=0;
while (1){
t++; ma=max(ma,t);
int w1=k1.getnext(),w2=k2.getnext();
if (w1==-1&&w2==-1) return 0;
if (w1==-1) return -1;
if (w2==-1) return 1;
if (w1<w2) return -1; else if (w1>w2) return 1;
}
}
int compare(int k1,int k2) {
return w[k1]<w[k2];
}
int checkcorrect(int l,int r){
bwtgen w(l,r);
vector<string>A;
for (int i=l;i<=r;i++){
string s=""; int now=i;
for (int j=1;j<=r-l+1;j++){
s+='0'+x[now];
if (now==r) now=l; else now++;
}
A.push_back(s);
}
sort(A.begin(),A.end());
// cout<<"fa "<<l<<" "<<r<<endl;
for (int i=0;i<(int)(A.size());i++){
int k1=w.getnext(),k2=A[i][r-l]-'0';
// cout<<k1<<" "<<k2<<endl;
assert(k1==k2);
}
return 0;
}
void solve(){
scanf("%d%d%d",&n,&m,&seed);
assert(1<=n&&n<=100000&&1<=m&&m<=100000&&0<=seed&&seed<=1000000000);
for (int i=1;i<=n;i++) x[i]=getrand()%2;
// for (int i=1;i<=n;i++) cerr<<x[i]; cerr<<endl;
len=0;
for (int i=1;i<=n;i++){
w[i]=0;
for (int j=1;j<=M;j++) w[i]=w[i]*2+x[i+j-1];
}
for (int i=1;i<=n;i++) a[i]=i;
sort(a+1,a+n+1,compare);
int pre=0;
for (int i=1;i<=n;i++)
if (a[i]<=n-M+1){
if (pre) assert(w[a[i]]!=w[pre]);
pre=a[i];
}
for (int i=1;i<=n;i++) ra[a[i]]=i;
for (int i=1;i<=n;i++) root[i]=insert(root[i-1],1,n,ra[i]);
int ti=0;
for (;m;m--){
ti++;
int l1=getrand()%n+1,r1=getrand()%n+1,l2=getrand()%n+1,r2=getrand()%n+1;
if (l1>r1) swap(l1,r1); if (l2>r2) swap(l2,r2);
// cerr<<l1<<" "<<r1<<" "<<l2<<" "<<r2<<endl;
// checkcorrect(l1,r1); checkcorrect(l2,r2);
bwtgen A(l1,r1),B(l2,r2);
printf("%d\n",check(A,B));
}
}
int main(){
int t; scanf("%d",&t);
assert(1<=t&&t<=3);
for (;t;t--) solve();
//cerr<<ma<<endl;
return 0;
}
C++11(clang++ 3.9) 解法, 执行用时: 2025ms, 内存消耗: 23896K, 提交时间: 2018-09-12 17:48:33
#include <bits/stdc++.h>
#define ALL(x) (x).begin(), (x).end()
#define ls(x) ((x) << 1)
#define rs(x) (ls(x) | 1)
#define mid ((l + r) >> 1)
#define lch ls(x), l, mid
#define rch rs(x), mid + 1, r
using VI = std::vector<int>;
using Pair = std::pair<int, VI::iterator>;
using VP = std::vector<Pair>;
const int M = 40;
const int max_N = (int) 1e5 + M + 21;
int T, n, m, seed, s[max_N];
inline int myRand() {
return seed = int((1ll * seed * 100000005 + 20150609) % 998244353);
}
__int128 hash[max_N];
inline __int128 getHash(int i, int len) {
return hash[i] >> (M - len);
}
VI seg[max_N << 2], vec1, vec2;
void build(int x, int l, int r) {
if (l == r) {
seg[x] = {l};
} else {
build(lch), build(rch);
seg[x].resize(seg[ls(x)].size() + seg[rs(x)].size());
std::merge(ALL(seg[ls(x)]), ALL(seg[rs(x)]), seg[x].begin(), [&](int a, int b) {
return hash[a] < hash[b];
});
}
}
int ql, qr, ll1, ll2;
VP qa1, qa2;
__int128 hash1[M + 21], hash2[M + 21];
void query(int x, int l, int r, VP &qa) {
if (ql <= l && r <= qr) {
qa.push_back({x, seg[x].begin()});
} else {
if (ql <= mid) query(lch, qa);
if (qr > mid) query(rch, qa);
}
}
inline int next(VP &qa, int l, int r, const __int128 *_hash, int ll, VI &vec) {
int ret = -1;
for (auto i = 0; i < qa.size(); ++i) {
int x = qa[i].first;
auto it = qa[i].second;
if (it == seg[x].end()) continue;
if (ret == -1 || hash[*it] < hash[*qa[ret].second]) ret = i;
}
if (!vec.empty()) {
if (ret == -1 || _hash[vec.back()] < hash[*qa[ret].second]) {
int pos = (ll + vec.back() - 1) + (r - l);
if (pos > r) pos -= (r - l + 1);
vec.pop_back();
return s[pos];
}
}
if (ret == -1) return -1;
int pos = *qa[ret].second + (r - l);
qa[ret].second++;
if (pos > r) pos -= (r - l + 1);
return s[pos];
}
inline void compare_init(VP &qa, int l, int r, __int128 *_hash, int &ll, VI &vec) {
qa.clear();
if (r - l >= M) {
ql = l, qr = r - M;
query(1, 1, n, qa);
}
ll = std::max(l, r - M + 1);
vec.clear();
for (int i = ll; i <= r; ++i) {
vec.push_back(i - ll + 1);
int len1 = r - i + 1, len2 = std::min(M, r - l + 1) - len1;
_hash[i - ll + 1] = (getHash(i, len1) << (M - len1)) | (getHash(l, len2) << (M - len1 - len2));
}
std::sort(ALL(vec), [&](int x, int y) { return _hash[x] > _hash[y]; });
}
inline int compare(int a, int b, int c, int d) {
compare_init(qa1, a, b, hash1, ll1, vec1);
compare_init(qa2, c, d, hash2, ll2, vec2);
while (true) {
int x = next(qa1, a, b, hash1, ll1, vec1);
int y = next(qa2, c, d, hash2, ll2, vec2);
// printf("x = %d, y = %d\n", x, y);
if (x != y) return (x < y) ? -1 : 1;
if (x == -1) return 0;
}
}
void testCase() {
scanf("%d%d%d", &n, &m, &seed);
// auto start_time = clock();
memset(s, 0, sizeof(s));
for (int i = 1; i <= n; ++i) s[i] = (myRand() & 1);
for (int i = 1; i <= n; ++i) {
hash[i] = 0;
for (int j = 0; j < M; ++j) {
(hash[i] <<= 1) |= s[i + j];
}
}
build(1, 1, n);
for (int i = 1; i <= m; ++i) {
int a = myRand() % n + 1, b = myRand() % n + 1;
if (a > b) std::swap(a, b);
int c = myRand() % n + 1, d = myRand() % n + 1;
if (c > d) std::swap(c, d);
int res = compare(a, b, c, d);
printf("%d\n", res);
}
// auto end_time = clock();
// printf("cost = %d ms\n", end_time - start_time);
}
int main() {
scanf("%d", &T);
while (T--) testCase();
return 0;
}
, then 
, the result of sorting will be 
, and the result string will be 
.
. Rikka knows it is easy to compare s1 with s2 in lexicographic order. To challenge you, Rikka wants you to compare f(s1),f(s2) in lexicographic order.%5D)
which satisfies for all index j ∈ [1,i), sj = tj and si < ti..
,
.
, let
, then
,
,
,
.