后：day1

衢州
2018.8.4

预计：30+50+10
实际：30+50+10

考试总结：

T1

没头绪。

T2

写完50分dp，之后就不会了。临近结束半小时，发现转移具有单调性。然后也没有写出，也不会用这个单调性做什么。

T3

一眼感觉是搜索+meet in the middle，数据范围刚好是。想到一个很麻烦的搜索（调不出来的搜索），然后到最后也没有想到什么。

总结：

T3没有再想别的，
T2感觉有单调性，直到最后才打表试了试，应该早试试。
加强码力，分配好时间。

题解：

T1

__builtin_popcount(x) 计算x的二进制下1的个数。

考虑两个二进制数，它们异或后的结果是：x的1 + y的1 - 两个数的某一位上都有的1（即异或后会同时消失的1）。
101011
110101
答案就是 4 + 4 - 4。

那么会发现，消掉的1，一次会消一对，同时消去两个。所以两个数是不是好的 只与 两个数二进制下1的个数总和是不是奇数有关。
那么就是要求x,y中一个数的二进制位下右奇数个，一个有偶数个。
那么统计答案就是统计奇数个1的个数 * 偶数个1的个数。

查询区间有多少个偶数个1的数 与 有奇数个1的数 => 查询区间有多少个偶数个1的数。（奇数个1的数可以用区间长度做差）
查询区间[l,r]中有多少个偶数个1的数=>查询区间[1,r]-区间[1,l-1]。

所以问题转化为：查询[1,m]中有多少个数 的二进制下有偶数个1。
0 1 2 3 4 5
(01)(23)(45)
两两一组，其中相邻的两个数的1的个数一奇一偶。
m是奇数：(m+1)/2
m是偶数：m/2+[m是否有偶数个1]

线段树离散化 或者 动态加点线段树。

T2

50分：将所有的奇数 往 偶数的空隙中放，f[i][j]表示第i个奇数，往偶数的第j个空隙中放的，逆序对最少是多少。
发现转移具有单调性，

首先求出原来序列的逆序对，然后计算将奇数放入后的贡献。
考虑每个奇数放到哪里。
将x放到i后面的贡献是：
$ans = \sum_{j=1}^i[b[j] > x] + \sum_{j=i+1}^{n} [x > b[j]]$
$ans = \sum_{j=1}^i[b[j] > x] + \frac{x}{2} - \sum_{j=1}^{i} [x > b[j]]$
$ans = \frac{x}{2} + \sum_{j=1}^{i} [b[j] > x] - [x > b[j]]$
第二步：因为小于x的数一共有x/2个，而i后面的小于x的数，可以用x/2-i前面小于x的数算出。
（其实这些式子没什么用）

假设当前已经知道了x放到每个i后面的答案，然后x变成了x+2，那么会发现只有x+1这个偶数会对答案产生变化，如果x+2在这个数前面放，那么答案原来的答案+1，否则-1。
所以就是查询最小值，区间求改，所以线段树可以做。

做法：
首先求出1放到每个位置的答案（因为1比所有偶数小，所以放到i后面答案就是i，放到0号位置就是0）。
然后求出最小值就是1的答案。
对于3，那么找到2的位置是pos，那么3放到pos前面的所有位置，就会产生原来的基础上增加1个逆序对，0~pos-1 加1，放到pos后面的所有位置，在原来的基础上减一，pos~n减1（1放到这里会有(2,1)这个逆序对，而3放到这里没有，所以-1）。
以此类推。在线段树上完成这些操作即可。

标程：
直接对式子的后面那一部分，用线段树维护，同样分为插入到pos前面和后面的情况，前面不变，后面-2。

T3

15分：状压dp。
三重容斥。

第一题的代码：

离散化：将所有端点坐标离散化

for (int i=1; i<=n; ++i) A[i] = read(), tmp[++m] = A[i];
sort(tmp+1,tmp+m+1);
int cnt = 1;
for (int i=2; i<=m; ++i) tmp[++cnt] = tmp[i];
int pos=lower_bound(tmp+1,tmp+1+m,A[i])-tmp;

然后在线段树时，即用tmp代替了原来的下标。

void Insert(int rt,int l,int r,int L,int R) ｛
    if (vis[rt]) return ;
    if (L <= l && r <= R) {
        sum[rt][0] = get(tmp[r]) - get(tmp[l]-1);
        sum[rt][1] = tmp[r] - tmp[l] + 1 - sum[rt][0];
        // ...
    ｝
    //...
｝
void query() {
    int l=lower_bound(tmp+1,tmp+1+m,L[i])-tmp; //l,r离散化后tmp中的的坐标，L[i],R[i]第i个查询
    int r=lower_bound(tmp+1,tmp+1+m,R[i]+1)-tmp-1; // 
    Insert(1,1,m,l,r); // m为所有端点的集合大小。
}

动态加点的线段树

void Insert(int &rt,LL l,LL r,LL L,LL R) {
    if (!rt) rt = ++CntNode;
    if (vis[rt]) return ;
    if (L <= l && r <= R) {
        sum[rt][0] = get(r) - get(l-1);
        sum[rt][1] = r - l + 1 - sum[rt][0];
        //...
    ｝
    //...
}
void query() {
    int l = read(), r = read();
    Insert(Root,1,1LL<<32,l,r);
}

标算（离散化）：

#include<stdio.h>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<cmath>
#include<iostream>
#include<assert.h>
#include<queue>
#include<string>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define rep(i,j,k) for (int i=(int)(j);i<=(int)(k);i++)
#define per(i,j,k) for (int i=(int)(j);i>=(int)(k);i--)
typedef long long LL;
const int N=210000;
LL f[34][2][2];
int ttmp[35];
LL get0(LL r){
    if(r==0)return 1;
    //0..r
    memset(f,0,sizeof f);
    int m=0;
    while(r){
        ttmp[++m]=(r%2);
        r/=2;
    }
    reverse(ttmp+1,ttmp+1+m);
    f[0][1][0]=1;
    rep(i,0,m-1)rep(eq,0,1)rep(v,0,1){
        rep(c,0,1){
            if(eq&&(c>ttmp[i+1]))continue;
            f[i+1][eq&(c==ttmp[i+1])][v^c]+=f[i][eq][v];
        }
    }
    return f[m][0][0]+f[m][1][0];
}
int n;
LL l[N],r[N];
LL tmp[N];
int m;
//si:[tmp[i],tmp[i+1]-1]
LL w[2];
int mes[N<<2];
void build(int me,int l,int r){
    mes[me]=r-l+1;
    if(l==r)return;
    int mid=(l+r)>>1;
    build(me<<1,l,mid);
    build(me<<1|1,mid+1,r);
}
void cov(int me,int l,int r,int x,int y){
    if(!mes[me])return;
    if(l==r){
        //printf("_%lld %lld\n",tmp[l],tmp[l+1]-1);
        LL cc=get0(tmp[l+1]-1)-get0(tmp[l]-1);
        w[0]+=cc;
        w[1]+=tmp[l+1]-tmp[l]-cc;
        mes[me]=0;
        return;
    }
    int mid=(l+r)>>1;
    if(x<=mid)cov(me<<1,l,mid,x,y);
    if(y>mid)cov(me<<1|1,mid+1,r,x,y);
    mes[me]=mes[me<<1]+mes[me<<1|1];
}
int main(){
    scanf("%d",&n);
    rep(i,1,n){
        scanf("%lld%lld",&l[i],&r[i]);
        tmp[++m]=r[i]+1;
        tmp[++m]=l[i];
    }
    sort(tmp+1,tmp+1+m);
    m=unique(tmp+1,tmp+1+m)-tmp-1;
    build(1,1,m);
    rep(i,1,n){
        int l1=lower_bound(tmp+1,tmp+1+m,l[i])-tmp;
        int r1=lower_bound(tmp+1,tmp+1+m,r[i]+1)-tmp-1;
        cov(1,1,m,l1,r1);
        unsigned long long ans=w[0]*w[1];
        printf("%llu\n",ans);
    }
    return 0;
}

我的代码（动态加点）：

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<iostream>
#include<cctype>
#include<set>
#include<map>
#include<queue>
#include<vector>
using namespace std;
typedef long long LL;
inline LL read() {
    LL x=0,f=1;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1;
    for(;isdigit(ch);ch=getchar())x=x*10+ch-'0';return x*f;
}
const int N = 800010;
LL sum[N][2];
int ls[N], rs[N], Root, CntNode;
bool vis[N];
LL get(LL x) {
    if (x & 1) return (x + 1) / 2 - 1; // 没有0，所以-1 
    return x / 2 + !(__builtin_popcount(x) & 1) - 1;
}
void Insert(int &rt,LL l,LL r,LL L,LL R) {
    if (!rt) rt = ++CntNode;
    if (vis[rt]) return ;
    if (L <= l && r <= R) {
        sum[rt][0] = get(r) - get(l-1);
        sum[rt][1] = r - l + 1 - sum[rt][0];
        vis[rt] = true;
        return ;
    }
    LL mid = (l + r) >> 1;
    if (L <= mid) Insert(ls[rt], l, mid, L, R);
    if (R > mid)  Insert(rs[rt], mid+1, r, L, R);
    sum[rt][1] = sum[ls[rt]][1] + sum[rs[rt]][1];
    sum[rt][0] = sum[ls[rt]][0] + sum[rs[rt]][0];
}
int main() {
    int n; cin >> n;
    for (int i=1; i<=n; ++i) {
        LL l = read(), r = read();
        Insert(Root, 1, 1LL<<32, l, r);
        printf("%lld\n",sum[Root][1] * sum[Root][0]);
    }
    return 0;
}

T2代码

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<cctype>
using namespace std;
typedef long long LL;
inline int read() {
    int x = 0, f = 1; char ch = getchar(); for (; !isdigit(ch); ch=getchar()) if (ch=='-') f = -1;
    for (; isdigit(ch); ch=getchar()) x = x * 10 + ch - '0'; return x * f;
}
const int N = 200100;
int pos[N], a[N];
struct BIT{
    int n, sum[N];
    void update(int p,int v) {
        for (; p<=n; p+=(p&(-p))) sum[p] += v;
    }
    int query(int p) {
        int ans = 0;
        for (; p; p-=(p&(-p))) ans += sum[p];
        return ans;
    }
}bit;
#define Root 1, 0, tn
#define lson rt << 1, l, mid
#define rson rt << 1 | 1, mid + 1, r
struct Seg{
    int tag[N << 1], Mn[N << 1];
    void pushup(int rt) {
        Mn[rt] = min(Mn[rt << 1], Mn[rt << 1 | 1]);
    }
    void pushdown(int rt) {
        if (tag[rt]) {
            tag[rt << 1] += tag[rt];
            tag[rt << 1 | 1] += tag[rt];
            Mn[rt << 1] += tag[rt];
            Mn[rt << 1 | 1] += tag[rt];
            tag[rt] = 0;
        }
    }
    void build(int rt,int l,int r) {
        if (l == r) {
            Mn[rt] = l;
            return ;
        }
        int mid = (l + r) >> 1;
        build(lson);
        build(rson);
        pushup(rt);
    }
    void update(int rt,int l,int r,int L,int R,int x) {
        if (L <= l && r <= R) {
            Mn[rt] += x;
            tag[rt] += x;
            return ;
        }
        pushdown(rt);
        int mid = (l + r) >> 1;
        if (L <= mid) update(lson, L, R, x);
        if (R > mid)  update(rson, L, R, x);
        pushup(rt);
    }   
}T;
int main() {
    int n = read(), tn = n / 2; 
    for (int i=1; i<=tn; ++i) 
        a[i] = read(), pos[a[i]] = i;
    bit.n = n;
    LL Ans = 0;
    for (int i=tn; i>=1; --i) {
        Ans += bit.query(a[i] - 1);
        bit.update(a[i], 1);
    }
    T.build(Root);
    for (int i=1; i<=n; i+=2) {
        Ans += T.Mn[1];
        T.update(Root, 0, pos[i + 1] - 1, 1);
        T.update(Root, pos[i + 1], tn, -1);
    }
    cout << Ans;
    return 0;
}