题解 P4117 【[Ynoi2018]五彩斑斓的世界】
officeyutong
2019-03-03 23:36:15
我们可以考虑使用AVX2指令集优化暴力。
先上代码。
```cpp
#pragma GCC target("avx,avx2")
#include <immintrin.h>
#include <cstdio>
#include <iostream>
using int_t = long long int;
using std::cin;
using std::cout;
using std::endl;
const int_t LARGE = 1e5;
int seq[LARGE + 1];
int n, m;
void modify(int* left, int* right, int val) {
__m256i addval = _mm256_set_epi32(val, val, val, val, val, val, val, val);
while (int_t(left) % 32 && left <= right) {
if (*left > val) *left -= val;
left++;
}
while (left + 7 <= right) {
__m256i curr = *(__m256i*)left;
*(__m256i*)left = _mm256_add_epi32(
curr, _mm256_mullo_epi32(_mm256_cmpgt_epi32(curr, addval), addval));
left += 8;
}
while (left <= right) {
if (*left > val) *left -= val;
left++;
}
}
int query(int* left, int* right, int val) {
int result = 0;
__m256i sum = _mm256_setzero_si256();
while (int_t(left) % 32 && left <= right) {
if (*left == val) result++;
left++;
}
__m256i tocmp = _mm256_set_epi32(val, val, val, val, val, val, val, val);
while (left + 7 <= right) {
sum = _mm256_sub_epi32(sum, _mm256_cmpeq_epi32(*(__m256i*)left, tocmp));
left += 8;
}
while (left <= right) {
if (*left == val) result++;
left++;
}
int* arr = (int*)∑
for (int i = 0; i < 8; i++) result += arr[i];
return result;
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) scanf("%d", &seq[i]);
for (int i = 1; i <= m; i++) {
int opt, left, right, x;
scanf("%d%d%d%d", &opt, &left, &right, &x);
if (opt == 1) {
modify(seq + left, seq + right, x);
} else {
printf("%d\n", query(seq + left, seq + right, x));
}
}
return 0;
}
```
首先本质上是一个暴力，然后考虑到AVX2指令集可以同时实现256位的整数运算，故可以每次处理序列中的8个整数，进而使得复杂度变为$O(nm/8)$。
大概实现思路：
#### 操作1
每次将8个整数与$x$进行比较，可以使用```_mm256_cmpgt_epi32```,如果某一个整数前者大于后者，则返回值中这个位置的值为$-1$,反之为0.
可以直接把返回结果与x相乘然后加到原数列上，然后复制回去即可。
#### 操作2
每次将八个整数与$x$进行比较，使用```_mm256_cmpeq_epi32```时，如果某个位置相等则该位置的值为$-1$,反之为$0$,直接累减每一次的比较结果即可。
### 参考资料
AVX和AVX2简单教程:https://www.codeproject.com/articles/874396/crunching-numbers-with-avx-and-avx
Intel官方参考手册:https://software.intel.com/sites/landingpage/IntrinsicsGuide/
### 其他
必须指定目标平台启用avx和avx2指令集才可以使用上述相关指令，故```#pragma GCC target("avx,avx2")```