题解 CF896E 【Welcome home, Chtholly】

**注：由于暂时没写正解，因此本文暂不提交题解，且可能没有严格遵守题解规范。** 题意简述：$n$ 个数，$m$ 次操作。操作一，将 $l\sim r$ 间所有大于 $x$ 的数减去 $x$；操作二，查询 $l\sim r$ 间恰好等于 $x$ 的数的个数。 --- 思路： 由乃题有啥好想的，直接去分块+卡常！但是……这题就有那么亿点点毒瘤，你怎么都不会。根据 > 没有什么是暴力解决不了的，如果有，那就去卡常。 的思想，你就去写了一个 $O(m\times n)$ 的暴力。~~然后去看看数据范围，发现是 $10^5$，就把写的东西删掉了。~~ 等等，你真的打算删掉？那你可能不知道**指令集**的强大之处！指令集可以帮你： > $n$ 方过百万，暴力碾标算！ 正如第一篇题解 [Link](/blog/finder-iot/solution-cf896e) 所说： > 对于这一题来说，在不更改数据大小，时间限制和内存限制的时候，如果我这个程序是正解，那么你可能可以很轻松地卡掉；但如果这个程序用的是指令集暴力，那么你想都别想。 不过我中间 TLE 过一次，原因也很简单：指令集没加够。 最终代码： ```cpp //By: Luogu@rui_er(122461) #pragma GCC optimize(2) #pragma GCC optimize(3) #pragma GCC optimize("Ofast") #pragma GCC optimize("inline") #pragma GCC optimize("-fgcse") #pragma GCC optimize("-fgcse-lm") #pragma GCC optimize("-fipa-sra") #pragma GCC optimize("-ftree-pre") #pragma GCC optimize("-ftree-vrp") #pragma GCC optimize("-fpeephole2") #pragma GCC optimize("-ffast-math") #pragma GCC optimize("-fsched-spec") #pragma GCC optimize("unroll-loops") #pragma GCC optimize("-falign-jumps") #pragma GCC optimize("-falign-loops") #pragma GCC optimize("-falign-labels") #pragma GCC optimize("-fdevirtualize") #pragma GCC optimize("-fcaller-saves") #pragma GCC optimize("-fcrossjumping") #pragma GCC optimize("-fthread-jumps") #pragma GCC optimize("-funroll-loops") #pragma GCC optimize("-fwhole-program") #pragma GCC optimize("-freorder-blocks") #pragma GCC optimize("-fschedule-insns") #pragma GCC optimize("inline-functions") #pragma GCC optimize("-ftree-tail-merge") #pragma GCC optimize("-fschedule-insns2") #pragma GCC optimize("-fstrict-aliasing") #pragma GCC optimize("-fstrict-overflow") #pragma GCC optimize("-falign-functions") #pragma GCC optimize("-fcse-skip-blocks") #pragma GCC optimize("-fcse-follow-jumps") #pragma GCC optimize("-fsched-interblock") #pragma GCC optimize("-fpartial-inlining") #pragma GCC optimize("no-stack-protector") #pragma GCC optimize("-freorder-functions") #pragma GCC optimize("-findirect-inlining") #pragma GCC optimize("-fhoist-adjacent-loads") #pragma GCC optimize("-frerun-cse-after-loop") #pragma GCC optimize("inline-small-functions") #pragma GCC optimize("-finline-small-functions") #pragma GCC optimize("-ftree-switch-conversion") #pragma GCC optimize("-foptimize-sibling-calls") #pragma GCC optimize("-fexpensive-optimizations") #pragma GCC optimize("-funsafe-loop-optimizations") #pragma GCC optimize("inline-functions-called-once") #pragma GCC optimize("-fdelete-null-pointer-checks") #pragma GCC optimize("unroll-loops") #pragma comment(linker, "/stack:200000000") #pragma GCC optimize("Ofast,no-stack-protector") #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") #include <bits/stdc++.h> using namespace std; const int N = 1e5+5; int n, m, a[N]; int main() { scanf("%d%d", &n, &m); for(int i=1;i<=n;i++) scanf("%d", &a[i]); while(m--) { int op, l, r, x; scanf("%d%d%d%d", &op, &l, &r, &x); if(op == 1) { for(int i=l;i<=r;i++) a[i] -= (a[i] > x) ? x : 0; } else { int ans = 0; for(int i=l;i<=r;i++) ans += (a[i] == x); printf("%d\n", ans); } } return 0; } ``` --- 但是以我们优（du）秀（liu）的品质，只把这题暴力过去怎么行呢？刚好有一道加强版：\[Ynoi2018\]五彩斑斓的世界 [Link](/problem/P4117) 我们发现内存限制缩小了，数据范围扩大了，只好去写正解。 思路： 【未完待续，以后有时间补】