Article From:https://www.cnblogs.com/Ressed/p/9967561.html

Consider the dis of two lines a and B

If the same: $| A-B | $

If it’s different: $n-| A-B |$.

Then consider three lines of dis, let’s say a & gt; = B & gt; = C

So there are four situations:

1.a,b,c 0/1The same kind: $| A-B |+ | a-c |+ | B-C |= 2a-2c $

2.aSame as b: $2n + 2c-2b $

3.aSame as C: $2n$

4.bSame as c: $2n + 2b-2a $

So we enumerate this B after sorting, and preprocess the prefix and suffix to be the maximum number, the minimum number and the total number of 0/1, then add one plus one, multiply one, and multiply the statistical answer.

Note that if int is used in weighting, it should be subtracted first and then explosion-proof.

 1 #include<bits/stdc++.h>
 2 #define CLR(a,x) memset(a,x,sizeof(a))
 3 using namespace std;
 4 typedef long long ll;
 5 typedef unsigned long long ull;
 6 typedef pair<int,int> pa;
 7 const int maxn=1e5+10,inf=1e9+7;
 8 
 9 inline ll rd(){
10     ll x=0;char c=getchar();int neg=1;
11     while(c<'0'||c>'9'){if(c=='-') neg=-1;c=getchar();}
12     while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
13     return x*neg;
14 }
15 
16 struct Node{
17     int v;ll n;
18     Node(int a=0,ll b=0){v=a,n=b;}
19 }f[2][maxn][3],g[2][maxn][3],ans;
20 int N,M;
21 pa a[maxn];
22 
23 inline void update(int v1,ll n1){
24     // printf("~%d %d\n",v1,n1);
25     if(!n1) return;
26     if(v1>ans.v) ans=Node(v1,n1);
27     else if(v1==ans.v) ans=Node(v1,n1+ans.n);
28 }
29 
30 int main(){
31     //freopen("","r",stdin);
32     int i,j,k;
33     N=rd(),M=rd();
34     for(i=1;i<=M;i++){
35         a[i].second=rd(),a[i].first=rd();
36     }sort(a+1,a+M+1);
37     f[0][0][1].v=f[1][0][1].v=g[0][M+1][1].v=g[1][M+1][1].v=inf;
38     for(i=1;i<=M;i++){
39         int tp=a[i].second,x=a[i].first;
40         memcpy(f[!tp][i],f[!tp][i-1],sizeof(f[1][1]));
41         if(x>f[tp][i-1][0].v) f[tp][i][0]=Node(x,1);
42         else if(x==f[tp][i-1][0].v) f[tp][i][0]=Node(x,f[tp][i-1][0].n+1);
43         else f[tp][i][0]=f[tp][i-1][0];
44         
45         if(x<f[tp][i-1][1].v) f[tp][i][1]=Node(x,1);
46         else if(x==f[tp][i-1][1].v) f[tp][i][1]=Node(x,f[tp][i-1][1].n+1);
47         else f[tp][i][1]=f[tp][i-1][1];
48         
49         f[tp][i][2].n=f[tp][i-1][2].n+1;
50     }
51     for(i=M;i;i--){
52         int tp=a[i].second,x=a[i].first;
53         memcpy(g[!tp][i],g[!tp][i+1],sizeof(g[1][1]));
54         if(x>g[tp][i+1][0].v) g[tp][i][0]=Node(x,1);
55         else if(x==g[tp][i+1][0].v) g[tp][i][0]=Node(x,g[tp][i+1][0].n+1);
56         else g[tp][i][0]=g[tp][i+1][0];
57         
58         if(x<g[tp][i+1][1].v) g[tp][i][1]=Node(x,1);
59         else if(x==g[tp][i+1][1].v) g[tp][i][1]=Node(x,g[tp][i+1][1].n+1);
60         else g[tp][i][1]=g[tp][i+1][0];
61         
62         g[tp][i][2].n=g[tp][i+1][2].n+1;
63     }
64     
65     for(i=2;i<=M-1;i++){
66         int tp=a[i].second,x=a[i].first;
67         int v1=2*g[tp][i+1][0].v-2*f[tp][i-1][1].v;ll n1=g[tp][i+1][0].n*f[tp][i-1][1].n;
68         update(v1,n1);
69         
70         v1=2*N-2*x+2*f[!tp][i-1][0].v,n1=f[!tp][i-1][0].n*g[tp][i+1][2].n;
71         update(v1,n1);
72         
73         v1=2*N,n1=f[!tp][i-1][2].n*g[!tp][i+1][2].n;
74         update(v1,n1);
75         
76         v1=2*N-2*g[!tp][i+1][1].v+2*x,n1=f[tp][i-1][2].n*g[!tp][i+1][1].n;
77         update(v1,n1);
78     }
79     printf("%I64d\n",ans.n);
80     return 0;
81 }

 

Link of this Article: Cf406E Hamming Triples

Leave a Reply

Your email address will not be published. Required fields are marked *