打了场div4 来补下题
D. Satyam and Counting
题目：
萨提亚姆在二维坐标平面上给出了 n 个不同的点。对于所有给定点 (xi,yi)，保证 0≤yi≤1,选择三个不同的点作为顶点，可以形成多少个不同的非世代直角三角形？如果有一个点 v 使得 v 是 a的顶点而不是 b的顶点，则两个三角形 a和 b 是不同的。 一个非整角直角三角形的面积为正，内角为 90∘

输入

第一行包含一个整数 t( 1≤t≤104 ) - 测试用例的数量。
每个测试用例的第一行包含一个整数 n ( 3≤n≤2⋅105) 点数。
接下来的 n 行包含两个整数 xi和 yi ( 0≤xi≤n , 0≤yi≤1)--Satyam 可以选择的 i'th 点。保证所有 (xi,yi) 都是成对的不同点。
保证所有测试用例中 n 的总和不超过 2⋅105。

输出
为每个测试用例输出一个整数，即从选择的三个点中可以形成的不同非分解直角三角形的个数。

样例：
Input
3
5
1 0
1 1
3 0
5 0
2 1
3
0 0
1 0
3 0
9
1 0
2 0
3 0
4 0
5 0
2 1
7 1
8 1
9 1
Output
4
0
8

思路：刚开始看到这个题无从下手,我们先读一遍题,题目的突破点是0≤yi≤1，，y轴的坐标只能是0或者1，那么好，我们第一种想到的情况是两个点的x坐标相同，y的坐标一个是0一个是1，那么这两个点和其他任何的点构成的三角形都是直角三角形,我们就找这种点，找到一个答案就加上n-2
第二种情况是
2，√2, √2的情况,
只要有三个点的x在范围内,并且其中两个点的y轴和另外的一个点的y轴不同即可，找到一个，答案就加上1

#include<bits/stdc++.h>
using namespace std;

typedef long long LL;
typedef pair<int,int> PII;
typedef pair<long long,long long> PLL;
typedef unordered_map<int,int> HashII;
typedef unordered_map<char,int> HashCI;
typedef priority_queue<int,vector<int>,greater<int>> heap;
typedef unsigned long long ULL;
typedef unordered_map<string,int> HashSI;
const int INF=0x3f3f3f3f;
const int N=2e5+10;
#define x first
#define y second
void solve()
{
    //---Dijkstra
    LL ans = 0;
    int n; cin>>n;
    vector<PLL> a(n+1);
    vector<int> c0(n+1),c1(n+1);//这个我们用来统计当坐标x为i的时候，这个点的y坐标是0还是1
    LL MMax = -INF;
    for(int i=0;i<n;i++){
        cin>>a[i].x>>a[i].y;
        if(a[i].y==0) c0[a[i].x]++;
        if(a[i].y==1) c1[a[i].x]++;
        MMax = max(MMax,a[i].x);
    }
    for(int i=0;i<=MMax;i++)
    {
        if(c0[i] && c1[i]) ans+=n-2;//找第一种情况
        if(i-2>=0 && c0[i] && c0[i-2] && c1[i-1]) ans++;//第二种情况
        if(i-2>=0 && c1[i] && c1[i-2] && c0[i-1]) ans++;
    }
    cout<<ans<<"\n";
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr),cout.tie(nullptr);
    int t ;
    cin>>t;
    while(t--)
    {
        solve();
    }
    return 0;
}

[========]

E. Klee's SUPER DUPER LARGE Array!!!

Klee 有一个长度为 n的数组 a ，其中按顺序包含整数 [k,k+1,...,k+n−1]。克利希望选择一个索引( 1≤i≤n)，使得 x=|a1+a2+⋯+ai−ai+1−⋯−an|最小。请注意，对于任意整数 z而言， |z|表示 z的绝对值。
输出 x 的最小值。
输入

第一行包含 t( 1≤t≤10^4) - 测试用例数。
每个测试用例包含两个整数 n和 k( 2≤n,k≤10^9)--数组的长度和数组的起始元素。
输出

对于每个测试用例，另起一行输出 x 的最小值。
Example
Input
4
2 2
7 2
5 3
1000000000 1000000000
Output
1
5
1
347369930

前言：当时D题没思路先做到E题，感觉是个等差数列，推了会公式，写出代码过了样例就交了，感觉可以过，结果。。。

#include<bits/stdc++.h>
using namespace std;

typedef long long LL;
typedef pair<int,int> PII;
typedef pair<long long,long long> PLL;
typedef unordered_map<int,int> HashII;
typedef unordered_map<char,int> HashCI;
typedef priority_queue<int,vector<int>,greater<int>> heap;
typedef unsigned long long ULL;
typedef unordered_map<string,int> HashSI;
const int INF=0x3f3f3f3f;
const int N=2e5+10;
string s;
int n;
void solve()
{
    //---Dijkstra
    LL n,k;
    cin>>n>>k;
    LL ans = INF;
    if(n % 2 == 0){
        LL sum1 = n/2 * n/2;
        //cout<<sum1<<"\n";
        LL x = k+n/2;
        //cout<<x;
        while(sum1>abs(sum1-2*x))
        {
            sum1-=2*x;
            x++;
        }
        //cout<<sum1<<"\n";
        ans = abs(sum1);
    }
    else
    {
        LL sum2 = ((2*k+3*(n-1)/2+1)*(n-1))/4-((2*k+(n-1)/2)*(n+1))/4;
        //cout<<sum2;
        LL x = k+(n-1)/2+1;
        while(sum2>abs(sum2-2*x)){
            sum2-=2*x;
            x++;
        }
        ans = abs(sum2);
    }
    cout<<ans<<"\n";
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr),cout.tie(nullptr);
    int t ;
    cin>>t;
    while(t--)
    {
        solve();
    }
    return 0;
}

废话少说，我之所以超时的原因是没注意到n，k的数据范围是0-1e9 超时是在所难免的
简单概括一下题目就是要求求前缀和后缀的最小差值,而且是具有单调性的，所以我们可以通过二分来做，（当然数学方法也是ok的）
当我们二分查找到差值最小的l时候，此时两者差值为正数，我们需要在计算一下l+1，因为负数我们也要考虑到

#include<bits/stdc++.h>
using namespace std;

typedef long long LL;
typedef pair<int,int> PII;
typedef pair<long long,long long> PLL;
typedef unordered_map<int,int> HashII;
typedef unordered_map<char,int> HashCI;
typedef priority_queue<int,vector<int>,greater<int>> heap;
typedef unsigned long long ULL;
typedef unordered_map<string,int> HashSI;
const int INF=0x3f3f3f3f;
const int N=2e5+10;
#define x first
#define y second
void solve()
{
    //---Dijkstra
    LL n,k;
    cin>>n>>k;
    LL sum = n*(k+k+n-1)>>1;//序列的总和
    LL ans = sum;
    int l = 0, r = n;
    while(l<r){//while(l<=r) 会死循环
        LL mid = (l+r+1)>>1;//当n为奇数的时候我们向上取整
        LL sum1 = mid*(2*k+mid-1)>>1;//左段序列的总和
        if(sum1<=sum-sum1) l = mid;
        else r = mid-1;
    }
    for(auto x : {l,l+1})
    {
        if(x>n) continue;
        LL sum2 = x*(k+k+x-1)>>1; 
         ans = min((LL)ans,abs(sum2-(sum-sum2)));
    }
    cout<<ans<<"\n";
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr),cout.tie(nullptr);
    int t ;
    cin>>t;
    while(t--)
    {
        solve();
    }
    return 0;
}