[原创]玲珑OJ 1098 && Round #11 C 萌萌哒的第三题 [并查集+思维]【数据结构】

int n,a,b,c;

int sum[N];
# define lowbit(x) (x&(-x))
void update(int index,int val){
    for(int i=index;i<=n;i+=lowbit(i))sum[i]+=val;
}
int getSum(int index){
    int ans = 0;
    for(int i=index;i>0;i-=lowbit(i))ans+=sum[i];
    return ans;
}

int Bsearch(int x){
    int l=0,r=n,ans=0,mid;
    while(l<=r){
        mid=(l+r)>>1;
        if(getSum(mid)>=x){
            ans = mid;
            r=mid-1;
        }
        else l=mid+1;
    }
    return ans;
}

int h[N],ind[N];
int main(){
    int _;
    scanf("%d",&_);
    while(_--){

        scanf("%d%d%d%d",&n,&a,&b,&c);
        make_data(n,a,b,c);
        for(int i=0;i<=n;i++)sum[i]=0,ind[i]=0,h[i]=0;
        //for(int i=0;i<n;i++)printf("%d ",num[i]);puts("");

        h[0]=1;update(num[0],1);ind[num[0]]=0;

        LL ji=1,he=0;
        for(int i=1,pre,id1,id2;i<n;i++){
            pre=getSum(num[i]);
            update(num[i],1);
            ind[num[i]]=i;
           // printf("%d  ",pre);

            id1 = Bsearch(pre);
            id2 = Bsearch(pre+1);

           // printf("%d %d  ",id1,id2);

            if(id1==0){
                id1 = ind[id1];
                h[i]=h[id1]+1;
                continue;
            }

            if(id2==0){
                id2 = ind[id2];
                h[i]=h[id2]+1;
                continue;
            }

            id1 = ind[id1];
            id2 = ind[id2];
           // printf("%d %d\n",id1,id2);
            h[i]=(h[id1]>h[id2]?h[id1]:h[id2])+1;


        }

        for(int i=0;i<n;i++){
            //printf("%d ",h[i]);
            he+=h[i];
            he = (he>MOD)?(he-MOD):he;
            ji*=h[i];
            ji%=MOD;
        }
        //puts("");
        printf("%lld %lld\n",he,ji);
    }
    return 0;
}

# include <stdio.h>
# include <stdlib.h>
# include <string.h>
# include <math.h>
# include <assert.h>
# include <vector>
# include <string>
# include <queue>
# include <map>
# include <set>
# include <iostream>
# include <algorithm>
# include <stack>

using namespace std;

# define foreach(it, s) for(__typedef(s.begin()) it = s.begin();it != s.end();it++)
# define sgn(x) ((x)<-eps?-1:(x)>eps)
typedef long long LL;
typedef pair<int, int> pii;


const int maxn = 1000000 + 10;
int n, num[maxn];
int ans[maxn];
pii fal[maxn], far[maxn];
int Left[maxn], Right[maxn];
const int Mod = 1000000000 + 7;

void rd(int Left, int Right, int a, int b, int c) {
    int len = Right - Left;
    long long rnum = b;
    for (int i=Left;i<Right;i++) {
        swap(num[i], num[i + rnum % len]);
        rnum = (rnum * a + b) % c;
        len--;
    }
}

void make_data(int n, int a, int b, int c) {
        for (int i=0;i<n;i++) num[i] = i + 1;
        int Left = 0, Right = min(110, n);
        for (;;) {
            rd(Left, Right, a, b, c);
            Left += 100;
            Right += 100;
            if (Left >= n) break;
            if (Right >= n) Right = n;
        }
}

int getfal(int r) {
    if (fal[r].first < 0) return r;
    return fal[r].first = getfal(fal[r].first);
}
int getfar(int r) {
    if (far[r].first < 0) return r;
    return far[r].first = getfar(far[r].first);
}

int main() {
    int T;
    int cas = 0;
    scanf("%d", &T);
    while (T--) {
        int a, b, c;
        scanf("%d%d%d%d", &n, &a, &b, &c);
        make_data(n, a, b, c);
        for (int i=0;i<=n+1;i++) {
            fal[i] = pii(-1, i);
            far[i] = pii(-1, i);
            ans[i] = -1;
            Left[i] = Right[i] = 0;
        }
        int fl, fr;
        for (int j=n-1;j>=0;j--) {
            int i = num[j];
            Left[i] = fal[getfal(i - 1)].second;
            Right[i] = far[getfar(i + 1)].second;

            fl = getfal(i - 1);
            fr = getfal(i);
            if (fal[fl].first > fal[fr].first) swap(fl, fr);
            fal[fl].first += fal[fr].first;
            fal[fr].first = fl;
            fal[fl].second = min(fal[fl].second, fal[fr].second);

            fl = getfar(i);
            fr = getfar(i + 1);
            if (far[fl].first > far[fr].first) swap(fl, fr);
            far[fl].first += far[fr].first;
            far[fr].first = fl;
            far[fl].second = max(far[fl].second, far[fr].second);
        }
        LL Y = 1, Z = 1;
        ans[num[0]] = 1;
        for (int i=1;i<n;i++) {
            ans[num[i]] = max(ans[Left[num[i]]], ans[Right[num[i]]]) + 1;
            Y = (Y + ans[num[i]]) % Mod;
            Z = Z * ans[num[i]] % Mod;
        }
        printf("%d %d\n", int(Y), int(Z));
    }
    return 0;
}