傳送門：http://www.lydsy.com/JudgeOnline/problem.php?id=2724
思路：首先我要說的是，題面真的有毒啊，，，
我不停WA發(fā)現(xiàn)讀錯了題，改了還WA發(fā)現(xiàn)又讀錯了，，一直該改改，，最后卡時過，，，我也是醉了，，，種類，，編號，，傻傻分不清啊！！
代碼：

#include<cstring> #include<iostream> #include<cstdio> #include<string> #include<algorithm> #include<cmath> #define N 40000 #define M 200 #define inf 1e9 using namespace std; int n,m,ll,num,a[N+5],a0[N+5],b[N+5],pos[N+5],maxi,maxj,c[M+5][N],c1[M+5][N], cnt[M+5][M+5],link1[N+5],s[N+5],t[N+5],l,r,lastans,w,ls,rs,id[N+5]; inline int getnum(){char c; int num;while (!isdigit(c = getchar()));num = c - '0';while (isdigit(c = getchar())) num = 10 * num + c - '0';return num; }void init(){n = getnum(); m = getnum();ll = ceil(sqrt(n)); num = 0;for (int i = 1;i <= n; ++i) a[i] = a0[i] = getnum();sort(a0 + 1,a0 + n + 1);b[0] = inf;for (int i = 1;i <= n; ++i) b[i] = upper_bound(a0 + 1,a0 + n + 1,a[i]) - a0 - 1;//for (int i = 1;i <= n; ++i) cout<<b[i]<<" ";//cout<<endl;for (int i = 1;i <= n; ++i) id[b[i]] = a[i]; for (int i = 1;i <= n; ++i) pos[i] = i/ll,num = max(num,pos[i]);//cout<<ll<<endl;//for (int i = 1;i <= n; ++i) cout<<pos[i]<<endl;pos[0] = -1; pos[n + 1] = -1;for (int i = 1;i <= n; ++i){if (pos[i] != pos[i - 1]) s[pos[i]] = i;if (pos[i] != pos[i + 1]) t[pos[i]] = i;}//for (int i = 0;i <= num; ++i) cout<<s[i]<<" "<<t[i]<<endl; }void make_it(){for (int i = 1;i <= n; ++i) c1[pos[i]][b[i]] ++;for (int i = 0;i <= num; ++i)if (i >= 1)for (int j = 1;j <= n; ++j)c1[i][j] += c1[i - 1][j];memset(cnt,0,sizeof(cnt));memset(link1,0,sizeof(link1));for (int i = num;i >= 0; --i) {maxi = maxj = 0;for (int j = i; j >= 0; --j){for (int k = t[j]; k >= s[j]; --k){c[i][b[k]] ++;if (c[i][b[k]] > maxi||c[i][b[k]] == maxi&&b[k] < b[maxj]) maxi = c[i][b[k]],maxj = k; }cnt[j][i] = maxj; }} }inline int ask(int l,int r){memset(link1,0,sizeof(link1));ls = pos[l],rs = pos[r];maxi = 0; maxj = 0;if (rs - ls <= 1) {for (int i = r; i >= l; --i){++link1[b[i]];if (link1[b[i]] > maxi||link1[b[i]] == maxi&&b[i] < b[maxj]) maxi = link1[b[i]],maxj = i;}}else {maxj = cnt[ls + 1][rs - 1];maxi = c1[rs - 1][b[maxj]] - c1[ls][b[maxj]];for (int i = s[rs];i <= r; ++i){++link1[b[i]];w = link1[b[i]] + c1[rs - 1][b[i]] - c1[ls][b[i]]; if (w > maxi||w == maxi&&b[i] < b[maxj]) {maxi = w;maxj = i; }}for (int i = t[ls];i >= l; --i){++link1[b[i]];w = link1[b[i]] + c1[rs - 1][b[i]] - c1[ls][b[i]];if (w > maxi||w == maxi&&b[i] < b[maxj]) maxi = w,maxj = i;}}return maxj; }void DO_IT(){lastans = 0;make_it();for (int j = 1;j <= m; ++j){l = getnum(); r = getnum();l = (l + lastans - 1)%n + 1; r = (r + lastans - 1)%n + 1;//cout<<l<<" "<<r<<endl;//cout<<l<<" "<<r<<endl;if (l > r) swap(l,r);lastans = a[ask(l,r)];printf("%d\n",lastans);} }int main(){//freopen("a.in","r",stdin);//freopen("a.out","w",stdout);init();DO_IT();//fclose(stdin); fclose(stdout);return 0; }

總結(jié)

以上是生活随笔為你收集整理的【bzoj2724】[Violet 6]蒲公英 （注意：题面有毒！）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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