http://oj.acm.zstu.edu.cn/JudgeOnline/problem.php?id=4440

題解：

由于x，y，z 都是大于等于1 的，
所以原序列是升序的，但是注意給你的a[0],a[1]可能不是升序的(這里要特別處理)。
對(duì)于這些操作很容易發(fā)現(xiàn)較長(zhǎng)的操作會(huì)覆蓋掉較小的操作
所以如果一個(gè)操作的區(qū)間比它后面的某個(gè)操作的區(qū)間小，那么這個(gè)操作是無(wú)效的，
可以發(fā)現(xiàn)有效的操作的區(qū)間必定是遞減的，
由于只會(huì)按照從大到小和從小到大排序，
而每個(gè)有效操作的有效區(qū)間是它下一個(gè)有效區(qū)間沒(méi)有覆蓋的部分，所以只需要把原序列
用雙指針維護(hù)，每次把每個(gè)有效操作的有效區(qū)間填好就行了。

#include<bits/stdc++.h> using namespace std; typedef long long LL; const int N = 1e5 + 10; const int mod = 1e9 + 7;int v[N], q[N]; int line[N]; int ans[N]; int n, qq; int main(){freopen("data.in","r",stdin);freopen("data.out","w",stdout);int t, x, y, z;scanf("%d", &t);while(t--){scanf("%d%d%d%d%d%d%d", &v[1], &v[2], &x, &y, &z, &n, &qq);for(int i = 3; i <= n; ++i) v[i] = (v[i - 1] * 1ll * x + y * 1ll * v[i - 2] + z) % mod;q[1] = v[1] % n + 1, q[2] = v[2] % n + 1;for(int i = 3; i <= qq; ++i) q[i] = (y * 1ll * q[i - 1] + x * 1ll * q[i - 2] + z) % n + 1;int en = 0, l = 1, r;for(int i = qq; i ; --i){if(q[i] > line[en]) line[++en] = q[i];}if(line[en] >= 2 && v[1] > v[2]) swap(v[2], v[1]);for(int i = line[en] + 1; i <= n; ++i) ans[i] = v[i];r = line[en];for(int i = en; i; --i){for(int j = line[i]; j > line[i - 1]; --j){if(line[i] & 1) ans[j] = v[l], l++;else ans[j] = v[r], r--;}}LL aans = 0;for(int i = 1; i <= n; ++i){aans += ans[i] * 1ll * i % mod;if(aans >= mod) aans -= mod;}printf("%I64d\n", aans);}return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的你听说过排序吗？的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。