[gym102769L]Lost Temple

考虑第$i$列的答案，即找到一个区间$[l,r]$，使得：

1.$l$和$r$要同奇偶，令$ans=\frac{r-l}{2}$，要求尽量大（$ans+1$即为该列答案）

2.$\forall 0\le j\le ans$，$[l+j,r-j]\subseteq [l_{i-j},r_{i-j}],[l_{i+j},r_{i+j}]$（两个都包含）

两个都包含可以看成求交，那么即$l\ge \max(l_{i-j},l_{i+j})-j$，类似的$r\le \min(r_{i-j},r_{i+j})+j$，很明显$l$和$r$都会取到端点，只需要保证长度足够，即$ans$合法当且仅当
$$
\min_{0\le j\le ans}(\min(r_{i-j},r_{i+j})+j)-\max_{0\le j\le ans}(\max(l_{i-j},l_{i+j})-j)\ge 2ans
$$
由于相邻两列答案至多相差1，记上一列的答案为$ans$，那么只需要判定$ans\pm 1$即可

注意到一次判定也就是求区间$l_{i}/r_{i}\pm i$最小和最大值，用树状数组维护复杂度过高，考虑用单调队列来维护，通过调整判定$ans\pm 1$的顺序每一次询问的右端点单调不下降，左端点至多减小1，复杂度为$o(n)$

时间复杂度为$o(n)$，且常数略大

 1 #include<bits/stdc++.h>

 2 using namespace std;

 3 #define N 5000005

 4 #define mod 998244353

 5 #define ull unsigned long long

 6 int t,n,ans,sum,mi[N],l[N],r[N];

 7 struct pqueue{

 8     int p,L,R,x,y,a[N],q[N];

 9     void add(int k){

10         while ((x<y)&&(a[k]<=a[q[y-1]]))y--;

11         q[y++]=k;

12     }

13     int query(int l,int r){

14         int ans=0x3f3f3f3f;

15         //q头尾为[x,y]，是[L,R]的单调队列，询问[l,r]

16         for(int i=l;i<L;i++)ans=min(ans,a[i]);

17         assert(R<=r);

18         while (R<r)add(++R);

19         if (L<l){

20             L=l;

21             while ((x<y)&&(q[x]<L))x++;

22         }

23         ans=min(ans,a[q[x]]);

24         return p*ans;

25     }

26 }Q[4];

27 ull calc(ull &A,ull &B){

28     ull T=A,S=B;

29     A=S;

30     T^=(T<<23);

31     T^=(T>>17);

32     T^=(S^(S>>26));

33     B=T;

34     return T+S;

35 }

36 void read(){

37     int L,X,Y;

38     ull A,B;

39     scanf("%d%d%d%llu%llu",&L,&X,&Y,&A,&B);

40     for(int i=1;i<=n;i++){

41         l[i]=calc(A,B)%L+X;

42         r[i]=calc(A,B)%L+Y;

43         if (l[i]>r[i])swap(l[i],r[i]);

44     }

45 }

46 void init(){

47     for(int i=0;i<4;i++)Q[i].L=Q[i].R=Q[i].x=Q[i].y=0;

48     for(int i=1;i<=n;i++)Q[0].a[i]=r[i]-i;

49     for(int i=1;i<=n;i++)Q[1].a[i]=r[i]+i;

50     for(int i=1;i<=n;i++)Q[2].a[i]=-(l[i]+i);

51     for(int i=1;i<=n;i++)Q[3].a[i]=-(l[i]-i);

52 }

53 bool check(int i,int ans){

54     if ((i+ans>n)||(i-ans<=0))return 0;

55     int r=min(Q[0].query(i-ans,i)+i,Q[1].query(i,i+ans)-i);

56     int l=max(Q[2].query(i-ans,i)-i,Q[3].query(i,i+ans)+i);

57     return r-l>=2*ans;

58 }

59 int main(){

60     mi[0]=1;

61     for(int i=1;i<N-4;i++)mi[i]=3LL*mi[i-1]%mod;

62     Q[0].p=Q[1].p=1;

63     Q[2].p=Q[3].p=-1;

64     scanf("%d",&t);

65     for(int ii=1;ii<=t;ii++){

66         scanf("%d",&n);

67         read();

68         init();

69         ans=0;

70         sum=1;

71         for(int i=2;i<=n;i++){

72             if (!check(i,ans))ans--;

73             else{

74                 if (check(i,ans+1))ans++;

75             }

76             sum=(sum+1LL*mi[i-1]*(ans+1))%mod;

77         }

78         printf("Case #%d: %d\n",ii,sum);

79     }

80 }

巴特西

[gym102769L]Lost Temple

最新文章

热门文章