树状数组和逆序对

算法

树状数组求逆序对

#include<bits/stdc++.h>
#define lowbit(x) x&(-x)
using namespace std;

typedef long long ll;
const int maxn=2e5+10;
int sum[maxn],cnt=maxn-1;

void add( int x ) {
    for(int i = x; i <= n; i += lowbit(i))
        sum[i] += 1;
}
int query( int x ) {
    int ans = 0;
    for(int i = x; i; i -= lowbit(i))
        ans += sum[i];
    return ans;
}  

int main()
{
    int n;
    cin>>n;
    ll ans=0;
    for( int i=1;i<=n;i++ ) 
    {
        int x;cin>>x;x=1e5+10-x;
        ans+=query(x-1);
        add(x);
    }
    cout<<ans<<endl;
}

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1010;

int n;
int tr[N], ans[N];

int lowbit(int x)
{
    return x & -x;
}

void add(int x, int v)
{
    for (int i = x; i <= n; i += lowbit(i))
        tr[i] += v;
}

int query(int x)
{
    int res = 0;
    for (int i = x; i; i -= lowbit(i))
        res += tr[i];
    return res;
}

int main()
{
    cin >> n;

    int sum = 0;
    for (int i = 0; i < n; i ++ )
    {
        int x;
        cin >> x;
        sum += query(n) - query(x);
        add(x, 1);
    }   

    return 0;
}

错数排列

错排数递推公式及其证明
求n个数的错排数：D P [ n ] = ( n − 1 ) ∗ ( D P [ n − 1 ] + D P [ n − 2 ] )
证明如下：
①考虑第n个元素，把它放在某一个位置，比如位置k，一共有n-1种放法
②考虑第k个元素，这时有两种情况：
（1）把它放到位置n，那么对于除n以外的n-1个元素，由于第k个元素放到了位置n，所以剩下n-2个元素的错排即可，有f ( n − 2 ) 种放法；
（2）第k个元素不放到位置n，这时对于这n-1个元素的错排，有f ( n − 1 ) 种放法。

舒适的奶牛

每次加入的奶牛只会影响周围四个奶牛的舒适，所以只需要枚举此奶牛加上它周围四个奶牛的舒适即可。

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 1010;

bool g[N][N];
int n;
int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};

int get(int x, int y) {
    int res = 0;
    for(int i = 0; i < 4; i ++) {
        int a = x + dx[i], b = y + dy[i];
        if(g[a][b])
            res ++;
    }
    return res;
}

int main() {
    cin >> n;
    int res = 0;
    int a, b;
    for(int i = 0; i < n; i ++) {
        scanf("%d%d", &a, &b);
        a ++, b ++;
        g[a][b] = true;
        if(get(a, b) == 3)
            res ++;
        
        for(int i = 0; i < 4; i ++) {
            int x = a + dx[i], y = b + dy[i];
            if(g[x][y]) {
                if(get(x, y) == 3)  res ++;
                else if(get(x, y) == 4) res --;
            }
        }
        printf("%d\n", res);
    }
    return 0;
}

牛的学术圈II

求出连续递增区间，如果某段区间没有连续递增，那么就会有“矛盾”，就可以区分出资历程度。

其他相同，则按字典序排序，想到连续递增区间。

如果用到if...else if... else，先写“严格”的条件，或者说“小”的条件。

#include<bits/stdc++.h>

using namespace std;

const int N = 110;

int n, m;
int g[N][N];
unordered_map<string, int> id;

int main() {
    cin >> m >> n;
    for(int i = 0; i < n; i ++) {
        string name;
        cin >> name;
        id[name] = i;
    }
    
    string s[N];
    while(m --) {
        for(int i = 0; i < n; i ++)     cin >> s[i];
        for(int i = 0; i < n; i ++) {
            int j = i + 1;
            while(j < n && s[j] > s[j - 1]) j ++;
            while(j < n) {
                int a = id[s[i]], b = id[s[j]];
                g[a][b] = 1;
                j ++;
            }
        }
    }
    
     for (int i = 0; i < n; i ++ )
    {
        for (int j = 0; j < n; j ++ )
            if (i == j) cout << 'B';
            else if (!g[i][j] && !g[j][i]) cout << '?';
            else if (!g[i][j]) cout << 1;
            else cout << 0;
        cout << endl;
    }
    return 0;
}

空调

这个题有点特别，它可以将一段区间的数+1或者-1，这就是区间修改，这个时候可以考虑差分。就是将原数组置为零，也就是将差分数组置为零。

差分数组只有两个操作，+1和-1，所以只要计算差分数组 正数和 和 负数和。

#include<iostream>

using namespace std;

const int N = 100010;

int n;
int a[N];

int main() {
    cin >> n;
    for(int i = 1; i <= n; i ++)     cin >> a[i];
    for(int i = 1; i <= n; i ++) {
        int x;
        cin >> x;
        a[i] -= x;
    }
    
    for(int i = n; i; i --)     a[i] -= a[i - 1];
    
    int pos = 0, neg = 0;
    for(int i = 1; i <= n; i ++) {
        if(a[i] > 0)    pos += a[i];
        else    neg -= a[i];
    }
    
    cout << max(pos, neg) << endl;
    return 0;
}