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 }```