H新型冠状爱情病毒

//由于新型冠状爱情病毒爆发，驻扎在深圳青螺湾的小蚯蚓蜗居在家里不敢出门，但是由于没有隔离好还是没有躲过这一灾难，所有蚯蚓都染上了这个病毒。蚯蚓们驻扎的社区也非常独特，每家每户都在同一排，每一户都有单独的一套房。对于蚯蚓社区的任意一段居住区间，该病毒在该区间的毒性为：该区间内患病指数第x大的蚯蚓居室（max_x_val）的和该区间内患病指数最大的蚯蚓居室（max_1_val）的异或值（max_x_val xor max_1_val）。当区间蚯蚓房子数小于x时，因为病毒数量不足以致病，所以可以视为没有毒性。聪明的你请快帮蚯蚓们算出他们小区所有区间段的病毒毒性之和，另外说一句，为什么蚯蚓们都会一起中爱情病毒呢，是因为他们是雌雄同体动物噢。输入要求
第一行先输入一个T（1 <= T <= 10）表示接下去有T组数据对于每组数据。第一行会有两个数，n和x（1 <= n <= 10^4，1 < x <= 100），如文中所描述。第二行会有n个数，对于每一个数，表示该房子的蚯蚓的中病指数总共为a_i（1 < a_i < 10^7），由于蚯蚓们体质都不同，所以在这一个社区里不会出现中病指数一样的房子。输出要求
对于每组数据，输出Case #i: val表示当前为第i组数据，该社区所有区间的蚯蚓毒性之和为val对于每行输出，最后没有空格，输出后直接换行输入
3  
3 2  
2 3 1  
5 2  
2 3 1 5 4  
5 3  
1 4 2 5 3  输出
Case #1: 4
Case #2: 24
Case #3: 38
小贴士
对于第一组样例可以构成的区间为：[2],[2, 3],[2, 3, 1],[3],[3, 1],[1]当x为2时，病毒会有毒性的区间为[2, 3], [2, 3, 1]和[3, 1]按照题目描述，所得的毒性分别为1，1，2，总和为4异或解释：异或，英文为exclusive OR，缩写成xor异或（xor）是一个数学运算符。它应用于逻辑运算。异或的数学符号为“⊕”，计算机符号为“xor”。其运算法则为：a⊕b = (¬a ∧ b) ∨ (a ∧¬b)

/* 
区间第x个和第1个的异或和。
因为数据不重复，先将数据构建成带下标的双向链表，将所有数排序后，从1到n遍历每个下标。
往左扫x个，往右扫x个，然后尺取x个数，就能知道当前区间第k个是谁。
扫的时候顺带维护x个前缀最大值和后缀最大值，就能知道第1大的值是谁。
转移的时候能很容易算到有多少区间第k大是自己，贡献也自然能算出来了。
由于是带下标的双向链表维护，读的时候是O(1)，删除的时候是O(1)，左右扫描x个，只是x常数级别。
总体来说时间复杂度是O(Tnx)。
*/ #include <iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
#define ll long long
#define N 10010
typedef struct node {int val, idx;
}Node;
Node a[N];
int num[N], pos[N], pre[N], nxt[N], lfmax[N], lf[N], rgmax[N], rg[N], n, x;
ll ans = 0;
bool cmp(Node a, Node b) {if (a.val < b.val)return true;elsereturn false;
}
void remove(int p) {int t1 = pre[p];int t2 = nxt[p];pre[t2] = t1;nxt[t1] = t2;
}
void count() {num[0] = num[n + 1] = -1;for (int i = 1;i <= n;i++) //构建成双向链表 {pre[i] = i - 1, nxt[i] = i + 1;}for (int i = 1;i <= n;i++){int p = pos[i], le = 0, ri = 0;lfmax[le] = num[p], rgmax[ri] = num[p];lf[le] = p, rg[ri] = p;le++, ri++;for (int j = 0, q = pre[p];j < x;j++, q = pre[q]){lfmax[le] = max(lfmax[le - 1], num[q]);lf[le] = q;le++;if (num[q] == -1)break;}for (int j = 0, q = nxt[p];j < x;j++, q = nxt[q]){rgmax[ri] = max(rgmax[ri - 1], num[q]);rg[ri] = q;ri++;if (num[q] == -1)break;}int a = le - 2;int b = x - (le - 2) - 1;while (a >= 0 && b < ri - 1){int mval = max(lfmax[a], rgmax[b]);   // 取出区间[p-a,p+b]的最大值 ans += 1LL * (lf[a] - lf[a + 1]) * (rg[b + 1] - rg[b]) * (num[p] ^ mval);a--, b++;}remove(p);}
}
int main() {int t, cnt = 1;scanf("%d", &t);while (t--){ans=0; scanf("%d%d", &n, &x);for (int i = 1;i <= n;i++){scanf("%d", &num[i]);a[i].val = num[i];a[i].idx = i;}sort(a + 1, a + n + 1, cmp);for (int i = 1;i <= n;i++){pos[i] = a[i].idx;    //记录第i小的数的位置 }count();printf("Case #%d: %lld\n", cnt, ans);cnt++;}return 0;
}