#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

typedef long long LL;

const int N = 100010;
int a[N],temp[N];

LL merge_sort(int l,int r)
{
    if(l >= r) return 0;
    int mid = l + r >> 1;
    //递归调用分别求左右两边的逆序对数量
    LL res = merge_sort(l,mid) + merge_sort(mid+1,r);

    int i = l, j = mid + 1, k = 0;
    while(i <= mid && j <= r)
    {
        if(a[i] <= a[j]) temp[k++] = a[i++];
        else
        {
            res += mid - i + 1;
            temp[k++] = a[j++];
        }
    }

    while(i <= mid) temp[k++] = a[i++];
    while(j <= r) temp[k++] = a[j++];

    for(int i=l,k=0; i<=r; i++,k++)
    {
        a[i] = temp[k];
    }
    return res;
}


int main()
{
    int n;
    cin >> n;
    for(int i=0; i<n; i++) scanf("%d",&a[i]);
    //归并排序求跨过mid的逆序对数量
    cout << merge_sort(0,n-1) <<endl;
    return 0;
}

思路

::::::::::::::::::::::::::::::::::
分批处理相同id的外卖店，用last数组存储最后一次接受订单的时间，分前后处理相同id，前面一段先减去没有订单的间隔时间，然后加上收到的订单数量*2并判断是否加入或者拿出优先队列，如果last[id]!=T的话，证明后面一段时间也是空闲的，所以要减去空闲的时间，并判断是否拿出优先队列；

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

const int N = 100010;
pair<int,int> order[N];

int st[N],score[N],last[N];
int n,m,T;

int main()
{
    cin >> n >> m >> T;
    for(int i=0; i<m; i++)
        scanf("%d %d",&order[i].first,&order[i].second);

    sort(order,order+m);    

    for(int i=0; i<m;)
    {
        int j = i;
        while(j < m && order[i] == order[j]) j++;
        int t = order[i].first, id = order[i].second, cnt = j - i;
        i = j;

        score[id] -= t - last[id] - 1;
        if(score[id] <= 3) st[id] = false;
        if(score[id] < 0) score[id] = 0;

        score[id] += cnt * 2;
        if(score[id] > 5) st[id] = true;

        last[id] = t;
    }

    for(int i=1; i<=n; i++)
    {
        if(last[i] < T)
        {
            score[i] -= T - last[i];
            if(score[i] <= 3) st[i] = false;
        }
    }

    int res = 0;
    for(int i=1; i<=n; i++) res += st[i];
    cout << res <<endl;
    return 0;
}

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 5010;
int s[N][N];

int main()
{
    int n,r;
    cin >> n >> r;
    r = min(r,5001);

    //让边界和r一样大，防止r的边界大于数据范围
    int mx = r, ny = r;
    for(int i=0; i<n; i++)
    {
        int x,y,w;
        scanf("%d %d %d",&x,&y,&w);
        x++,y++;
        s[x][y] += w;
        mx = max(mx,x);
        ny = max(ny,y);
    }

    for(int i=1; i<=mx; i++)
        for(int j=1; j<=ny; j++)
            s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] + s[i][j];

    int res = 0;
    for(int i=r; i<=mx; i++)
        for(int j=r; j<=ny; j++)
            res = max(s[i][j] - s[i-r][j] - s[i][j-r] + s[i-r][j-r], res);

    cout << res << endl;
    return 0;
}

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 100010;
long long a[N],s[N],cnt[N];

int main()
{
    int n,k;
    cin >> n >> k;
    for(int i=1; i<=n; i++)
    {
        scanf("%d",&a[i]);
        s[i] = s[i-1] + a[i];
    }

    long long res = 0;
    cnt[0]++;
    for(int i=1; i<=n; i++)
    {
        res += cnt[s[i] % k];
        cnt[s[i] % k] ++;
    }

    cout << res <<endl;
    return 0;
}

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 1010;
int a[N][N],s[N][N];

int main()
{
    int n,m,q;
    cin >> n >> m >> q;
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++)
            scanf("%d",&a[i][j]);

    //创建前缀和
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++)
            s[i][j] = s[i-1][j] + s[i][j-1] -s[i-1][j-1] + a[i][j];

    for(int i=0; i<q; i++)
    {
        int x1,y1,x2,y2;
        cin >> x1 >> y1 >> x2 >> y2;
        cout << s[x2][y2] - s[x1-1][y2] - s[x2][y1-1] + s[x1-1][y1-1] << endl;
    }
    return 0;
}

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;

const int N = 100010;
int a[N],s[N];

int main()
{
    int n,m;
    cin >> n >> m;
    for(int i=1; i<=n; i++)
    {
        scanf("%d",&a[i]);
        s[i] = s[i-1] + a[i];
    }

    for(int i=0; i<m; i++)
    {
        int l,r;
        cin >> l >> r;
        cout << s[r] - s[l-1] << endl;
    }
    return 0;
}

#include <iostream>
#include <algorithm>
using namespace std;

typedef long long LL;
const int N = 100010;
int a[N],s[N];

int main()
{
    int n;
    cin >> n;
    for(int i=1; i<=n; i++)
    {
        scanf("%d",&a[i]);
        s[i] = s[i-1] + a[i];
    }

    if(s[n] % 3) puts("0");
    else
    {
        LL cnt = 0, res = 0;
        for(int i=3; i<=n; i++)
        {
            if(s[i-2] == s[n] / 3) cnt++;
            if(s[n] - s[i-1] == s[n] / 3) res += cnt;
        }
        cout << res;
    }
    return 0;
}

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;

int days[13] = {0,31,28,31,30,31,30,31,31,30,31,30,31};

bool checkvalid(int year,int month,int day)
{
    if(!month || month > 12) return false;
    if(day == 0) return false;
    if(month != 2) 
    {
        if(day > days[month])
            return false;
    }
    else
    {
        int leap = (year % 4 == 0 && year % 100 != 0 || year % 400 == 0);
        if(day > 28 + leap) return false;
    }
    return true;
}

void printdate(int date)
{
    printf("%04d-%02d-%02d\n",date / 10000,date % 10000 / 100,date % 100);
}

int main()
{
    //读入日期
    int a,b,c;
    scanf("%d/%d/%d",&a,&b,&c);

    for(int i=19600101; i<=20591231; i++)
    {
        int year = i / 10000;    
        int month = i % 10000 / 100;
        int day = i % 100;
        if(checkvalid(year,month,day))
        {
            if((year % 100 == a && month == b && day == c) //年月日
                    ||(month == a && day == b && year % 100 == c) //月日年
                    || (day == a && month == b && year % 100 == c)) //日月年
                            printdate(i);
        }
    }

    return 0;
}

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;

int main()
{
    int w,m,n;
    cin >> w >> m >> n;

    m--,n--;
    int x1 = m / w, x2 = n / w;
    int y1 = m % w, y2 = n % w;
    if(x1 % 2) y1 = w - 1 - y1;
    if(x2 % 2) y2 = w - 1 - y2;

    cout << abs(x1-x2) + abs(y1-y2) << endl; 
    return 0;
}

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 100010;

void merge_sort(int *q,int left,int right,int *temp)
{
    if(left>=right) return;

    int mid = left + right >> 1;
    merge_sort(q,left,mid,temp),merge_sort(q,mid+1,right,temp);

    int index = 0, i = left, j = mid + 1;
    while(i <= mid && j <= right)
    {
        if(q[i] <= q[j]) temp[index++] = q[i++];
        else temp[index++] = q[j++];
    }
    while(i <= mid) temp[index++] = q[i++];
    while(j <= right) temp[index++] = q[j++];
    for(int i=left,j=0; i<=right; i++,j++) q[i] = temp[j];

}

int main()
{
    int q[N];
    int n;
    cin >> n;
    for(int i=0; i<n; i++) scanf("%d",&q[i]);

    int *temp = (int *)malloc(sizeof(int)*n);
    merge_sort(q,0,n-1,temp);

    for(int i=0; i<n; i++) printf("%d ",q[i]);
    return 0;
}