首页 > 代码库 > （ST表+二分+前缀和）CSU 1879 - Hack Protection
（ST表+二分+前缀和）CSU 1879 - Hack Protection
题意：
给定一个序列，求异或和与按位与和相同的区间有几个。
异或和：n个数异或起来。按位与和类似。
分析：
这才是神题，基础算法大杂烩。
问大佬这题的时候，人家只说很不难啊。。
只能说自己太菜。
由于询问区间个数，自然要快速知道某一个区间的异或和与按位与和。
异或和很简单，利用他的性质，直接求前缀和即可。
但是按位与没有和加法和异或类似的性质，无法直接求出。
但是利用之前的知识可以将所有结果预处理出来，而且只要nlogn的复杂度。
就是之前搞RMQ的ST表，很适合离线查询。
几乎不用动的把 min或max换成&，就能得到O(1)查询区间按位与和的方法。
此时，依然无从下手。
我们还需要知道一个性质，就是说按位与是单调递减的！
因为二进制表示中，1不会增多，只会减少，再确切一点在32位int整数中只会减少32次，最多！
所以最后只会出来类似999998877444422222221110000000这样的值。
也就是说固定每一位左端点，从左端点按位与到最后一位都是出现想上面这样类似的数列。
这时我们就能发现
假设当前固定左端点为L，第一个9的开头是R，9的结尾是W，i为从R到W。
异或前缀和用pre数组表示。
那么那么如果要是异或和和按位与相等。
必须要满足pre[i]^pre[L-1]==9
我们需要统计的是满足这样条件的i的数量。
但是显然不能使用暴力的方式。
继续利用异或的性质，a^b=c ==> a=c^b
我们可以知道pre[i]==9^pre[L-1]
此时我们只要找前缀和里有几个是满足这个条件的。
这里又是一个非常牛逼的方法，直接用map<int,vector<int>>记录每一个前缀异或和的所有下标。
还记得当年的有序数列计数操作么？
upper_bound - lower_bound。。。。
最终复杂度O(n*log(ai)*log(n))
到此，所有题解都结束了，又回忆了一次，只想说好牛逼。。
绝对好题。。
代码：
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #include <map> 5 #include <iostream> 6 #include <vector> 7 8 9 10 using namespace std;11 12 const int inf = 0x3f3f3f3f;13 const int maxn = 100010;14 15 #define fi first16 #define se second17 typedef long long ll;18 typedef pair<int, int> pii;19 20 int n;21 int num[maxn];22 int pre[maxn];23 24 int st[maxn];25 int dp[maxn][20];26 27 map<int, vector<int> > xo;28 29 void init() {30 pre[0] = 0;31 xo.clear();32 }33 34 void Build_ST() {35 st[0] = -1;36 for(int i = 1; i <= n; i++) {37 st[i] = ((i & (i - 1)) == 0) ? st[i - 1] + 1 : st[i - 1];38 dp[i][0] = num[i];39 }40 for(int j = 1; j <= st[n]; j++) {41 for(int i = 1; i + (1 << (j - 1)) <= n; i++) {42 dp[i][j] = dp[i][j - 1] & dp[i + (1 << (j - 1))][j - 1];43 }44 }45 }46 47 int ga(int l, int r) {48 int k = st[r - l + 1];49 return dp[l][k] & dp[r - (1 << k) + 1][k];50 }51 52 int gr(int zl, int l, int b) {53 int left = l, right = n;54 int w = l + 1;55 while(left <= right) {56 int mid = (left + right) >> 1;57 int pp = ga(zl, mid);58 if(pp == b) {59 left = mid + 1;60 w = mid;61 } else {62 right = mid - 1;63 }64 }65 return w;66 }67 68 69 int main() {70 // freopen("hack.in", "r", stdin);71 // freopen("hack.out", "w", stdout);72 scanf("%d", &n);73 init();74 for(int i = 1; i <= n; i++) {75 scanf("%d", &num[i]);76 pre[i] = pre[i - 1] ^ num[i];77 xo[pre[i]].push_back(i);78 }79 Build_ST();80 ll ans = 0;81 for(int i = 1; i <= n; i++) {82 int w = i - 1;83 int q = 2147483647;84 for(int r = w; r < n; r = w) {85 q &= num[r + 1];86 w = gr(i, r + 1, q);87 int d = pre[i - 1] ^ q;88 ans += upper_bound(xo[d].begin(), xo[d].end(), w) - lower_bound(xo[d].begin(), xo[d].end(), r + 1);89 }90 }91 printf("%lld\n", ans);92 return 0;93 94 }
（ST表+二分+前缀和）CSU 1879 - Hack Protection