上午
(睡觉ing)
主要也就是讲了数据结构
讲了树状数组，线段树的相关操作（貌似没有提到分块）
单改区查
秒切
区改单查
搞个差分数组，还是切
区改区查
推式子....
p的前缀和=egin{aligned}sum_{i=1}^p a[i] = sum_{i=1}psum_{j=1}i d[j]end{aligned}
其中d数组为差分数组
在等式最右侧的式子(egin{aligned}sum_{i=1}^psum_{j=1}^id[j]end{aligned}) 中，(d[1])被利用了(p)次，(d[2])(被利用了)(p-1)次…….,因此我们可以推出
p的前缀和= egin{aligned}sum_{i=1}psum_{j=1}id[j] = sum_{i=1}^pd[i]*(p-i+1)end{aligned}
然后我们考虑将(p+1)与(-i) 提出来
p的前缀和=(egin{aligned}(p+1)*sum_{i=1}^pd[i]-sum_{i=1}^pd[i]*iend{aligned})
那么我们考虑维护两个数组的前缀和：一个数组是(sum1[i] = d[i]),另一个是(sum2[i] = d[i]*i)
查询的时候位置p的前缀和为：((p+1)*sum1)数组中p的前缀和-(sum2)数组中p的前缀和
区间[(l,r])的和即：位置(r)的前缀和 - 位置(l-1)的前缀和。
修改的时候对sum1数组正常差分
对(sum2)数组类似，对(sum2[i])加上(l*x)，给(sum2[r+1])减去((r-1)*x)
Code
inline void jia (int x, int val) {
for (int i = x; i <= n; i += lowbit(i))
sum1[i] += val, sum2[i] += val*x;
}
inline void qujianjia (int l, int r, int val) {jia(l, val), jia(r+1, -val);}
inline int chaxun(int x) {
int res(0);
for (int i = x; i; i -= lowbit(i))
res += (x + 1)*sum1[i] - sum2[i];
return res;
}
inline int qujianchaxun(int l, int r) {return chaxun(r) - chaxun(l-1);}
逆序对
way1.我们可以用归并排序来求
如果我们想将一个序列拍成有序的，那么每次合并的时候，左右两边的序列一定是有序的
我们每次只需要考虑右边的数能与左边的数分别构成多少个逆序对
看个例子左区间(a = left{5,6,7 ight})右区间 (b = left{1, 2, 9 ight})
1. 5 > 1, 发现产生了逆序对， 此时做区间没有合并的数都要比1大，所以1与左边区间共产生了三个逆序对
2. 5 > 2, 由上文可知产生了产生了三对逆序对
….
所以：
tot += (LL)mid - i + 1;
复杂度(nlogn)
way2.用树状数组当然是建立权值树状数组
我们考虑逆序对的定义，首先是(i>j)，其次是(a[i] < a[j])
在树状数组里面，对于权值树状数组，我们肯定考虑离散化
对于每次新进的数x，我们考虑在树状数组上在下标为x的地方加1，代表这个数存在过
而我们再来思考逆序对的定义，说白了就是在当前这个数的前面，有多少个比ta大的
求一遍(1) ~ (x)这个数的前缀和，再用一共输入的点的个数前去这部分，不就剩下了比x大的部分？
PS:(rank[i])表示原序列中第(i)个数目前的排名（大小）是多少
#include <bits/stdc++.h>
#define int long long
#define lowbit(x) (x&-x)
using namespace std;
const int N = 5e5+66;
int n, m, tot;
int rank[N], tree[N];
struct node {int val, id;}a[N];
inline int cmp (node x, node y) {
return (x.val<y.val)||(x.val == y.val && x.id < y.id);
}
inline void charu (int x, int val) {
for (int i = x; i <= n; i += lowbit(i))
tree[i] += val;
}
inline int chaxun (int x) {
int res = 0;
while (x) {
res += tree[x];
x -= lowbit(x);
}
return res;
}
signed main () {
cin >> n;
for (int i = 1; i <= n; ++ i) {
cin >> a[i].val;
a[i].id = i;
}
sort (a + 1, a + n + 1, cmp);
for (int i = 1; i <= n; ++ i) rank[a[i].id] = i;
for (int i = 1; i <= n; ++ i) {
charu(rank[i], 1);
tot += i-chaxun(rank[i]);
}
cout << tot;
return 0;
}
小火柴
考虑，我们需要保证的是，a序列的第k大数对应着b序列中第k大的数
所以在离散化完成后的数组内，我们假设(a = left{ 4,3,1,2 ight}),(b = left{ 1,3,2,4 ight})
令(q[a[i]] = b[i])，相当于以(a[i])为关键字对(b[i])进行排序
得到(q[1] = 2, q[2] = 4, q[3] = 3, q[4] = 1)，意味着，a中的1对应着b中的2，a中的2对应着b中的4
若序列a与序列b相等，也就是说(q[i] = i)
我们想让(a,b)序列相等，就要保证q数组单调递增
所以原来问题转化为：将原来凌乱的q数组转化为一个升序数组需要的最小次数，且每一次只能交换相邻的两个数
这不是逆序对这是啥？
项链
用(nlogn)离线树状数组才能做，莫队会被卡
我们首先肯定要把询问按照右端点从小到大排序，这样保证我们不会来回跳转
然后我们考虑当前这个颜色是否出现过，如果发现没有出现过，那么就令他为(1)，如果出现过，就令前面出现的那次(+(-1))，这次为(1)
此时我们考虑两种情况，
第一种：上次出现的颜色在当前查询的区间内，那么我们新规定的颜色，完全可以取代上一次的，题目在询问我们有多少种颜色，并不在乎出现次数
第二种，上次出现的颜色不在当前查询的区间内，那更好，我们之前的修改完毕之后，我们以后肯定不会再用它，因为我们的r是从前往后扫的
每次查询的时候，我们就查询这个区间的l与r之间存在多少个1，利用树状数组可以很好的完成
#include <bits/stdc++.h>
// #define debug
#define lowbit(x) (x&-x)
using namespace std;
const int N = 2e6+66;
int n, m;
int a[N], ans[N];
int vis[N], tree[N];
struct node {int l, r, id;}q[N];
inline int cmp (node x, node y) {return x.r < y.r;}
inline void charu (int x, int val) {
for (int i = x; i <= n; i += lowbit(i))
tree[i] += val;
}
inline int chaxun (int x) {
int res = 0;
while (x) {
res += tree[x];
x -= lowbit(x);
}
return res;
}
int main () {
scanf ("%d", &n);
for (int i = 1; i <= n; ++ i) scanf ("%d", &a[i]);
scanf ("%d", &m);
for (int i = 1; i <= m; ++ i) {
int l, r;
scanf ("%d%d", &q[i].l, &q[i].r);
q[i].id = i;
}
sort(q+1, q+m+1, cmp);
int now = 1;
for (int i = 1; i <= n; ++ i) {
if (!vis[a[i]]) {
vis[a[i]] = i;
charu(i, 1);
} else {
charu(vis[a[i]], -1);
charu(i, 1);
vis[a[i]] = i;
}
while (q[now].r == i) {
ans[q[now].id] = chaxun(q[now].r) - chaxun(q[now].l-1);
#ifdef debug
cout << "now:-->" << now << '
';
#endif
++ now;
}
}
#ifdef debug
printf ("
");
#endif
for (int i = 1; i <= m; ++ i) cout << ans[i] << '
';
return 0;
}
异或和
题目是在求所有连续和的异或之和，即：(oplus sum_limits{i=1}^nsum_limits{j=0}^{i-1}sum(i)-sum(j))
观察数据范围，(sum_limits{i=1}^{n}a[i] leq 1e6) --> 考虑前缀和
考虑二进制下每一位对答案的影响，所以分四种情况
设第一个数(A)，第二个数为(B)，所以分为(A=1)(B=1)(A=1)(B=0)的情况
(1 - 1 = 1)
说明第一个数的第(k)位为(1)的时候，前(k-1)位要比(B)的前(k-1)位小
(1 - 0 = 1)
说明第一个数的第(k)位为(1)的时候，前(k-1)位要比(B)的前(k-1)位大
(0 - 1 = 0)
说明第一个数的第(k)位为(0)的时候，前(k-1)位要比(B)的前(k-1)位小
(0 - 1 = 1)
说明第一个数的第(k)位为(0)的时候，前(k-1)位要比(B)的前(k-1)位大
然后埋坑.....
附近公园
先把这个序列大于等于水面的取为1，否则为0
考虑每一位置对他左边的取一个min和max，考虑min与max序列中，“1”的那些位置有几个不一样
就相当于存在了几对区间，所以
ans = differt >> 1;
然后我们考虑用min和max来围护一个什么东西，用离散化加树状数组就好
关于可持久化线段树
考虑对每一个状态都开一个线段树，为了使其优化，我们尝试当前树连之前树的边，这样会优化空间
单点修改的话，可以简单一些
对于区间修改的东西，我们得边读入边建树
而对于可持久化权值线段树，也就是主席树（jmh树）
我不会...
不会就要学啊！等我回头补上！！！
下午
讲了一下午树剖，不懂..... click
晚上
写博客 补坑