2821: 作詩(Poetize)

Time Limit: 50 Sec??Memory Limit: 128 MB
Submit: 3300??Solved: 965
[Submit][Status][Discuss]

Description

神犇SJY虐完HEOI之后給傻×LYD出了一題：SHY是T國的公主，平時的一大愛好是作詩。由于時間緊迫，SHY作完詩 之后還要虐OI，于是SHY找來一篇長度為N的文章，閱讀M次，每次只閱讀其中連續的一段[l,r]，從這一段中選出一 些漢字構成詩。因為SHY喜歡對偶，所以SHY規定最后選出的每個漢字都必須在[l,r]里出現了正偶數次。而且SHY認 為選出的漢字的種類數（兩個一樣的漢字稱為同一種）越多越好（為了拿到更多的素材！）。于是SHY請LYD安排選 法。LYD這種傻×當然不會了，于是向你請教……問題簡述：N個數，M組詢問，每次問[l,r]中有多少個數出現正偶 數次。

Input

輸入第一行三個整數n、c以及m。表示文章字數、漢字的種類數、要選擇M次。第二行有n個整數，每個數Ai在[1, c ]間，代表一個編碼為Ai的漢字。接下來m行每行兩個整數l和r，設上一個詢問的答案為ans(第一個詢問時ans=0)， 令L=(l+ans)mod n+1, R=(r+ans)mod n+1，若L>R，交換L和R，則本次詢問為[L,R]。

Output

輸出共m行，每行一個整數，第i個數表示SHY第i次能選出的漢字的最多種類數。

Sample Input

5 3 5
1 2 2 3 1
0 4
1 2
2 2
2 3
3 5

Sample Output

2
0
0
0
1

HINT

對于100%的數據，1<=n,c,m<=10^5

Source

?

【題解】

不知是什么原因，我用上次做蒲公英的寫法寫這道題，T了。。。

改用陳立杰論文的寫法，又T了。。。

?

“寫這個題以后，我也沒干別的，大概三個寫法，第一個，就是vector存位置二分它，第二個，就是分塊排序二分，第三個，就是預處理每個塊中每個數出現次數。如果說還有一點優化，就是加了輸出優化，這個對時間秒殺hzw題解意義很重大的，還有取摸優化也是很重要的。很慚愧，就做了一點微小的工作，謝謝大家。” ——姜則岷

發現蒲公英也可以用這個寫法，更快。。

設塊大小為m預處理p[i][j]表示第i塊到第j塊有多少出現偶數次的，復雜度n^2/m

預處理pp[i][j]表示第i塊，j出現了多少次，然后做前綴和，復雜度m * n（數的個數與n相同）

查詢時，中間塊直接獲得，兩邊的數依次枚舉，查詢pp，根據奇偶分情況討論，復雜度nm（詢問次數與n相同）

總復雜度m * n + nm + n^2/m,設m = n^x

2 * n^(x + 1)? + n^(2 - x) <= 4√n^3? 當且僅當x + 1 = 2 - x，即x = 0.5時取等號

m = √n

?

1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cstdlib> 5 #include <algorithm> 6 #include <queue> 7 #include <vector> 8 #include <map> 9 #include <string> 10 #include <cmath> 11 #include <sstream> 12 #define min(a, b) ((a) < (b) ? (a) : (b)) 13 #define max(a, b) ((a) > (b) ? (a) : (b)) 14 #define abs(a) ((a) < 0 ? (-1 * (a)) : (a)) 15 template<class T> 16 inline void swap(T &a, T &b) 17 { 18 T tmp = a;a = b;b = tmp; 19 } 20 inline void read(int &x) 21 { 22 x = 0;char ch = getchar(), c = ch; 23 while(ch < '0' || ch > '9') c = ch, ch = getchar(); 24 while(ch <= '9' && ch >= '0') x = x * 10 + ch - '0', ch = getchar(); 25 if(c == '-') x = -x; 26 } 27 const int INF = 0x3f3f3f3f; 28 const int MAXN = 100000 + 10; 29 const int SMAXN = 320; 30 int size,group,l[SMAXN],r[SMAXN],num[MAXN],n,c[MAXN],m,typ,p[SMAXN][SMAXN],sum[SMAXN][MAXN]; 31 inline int find(int ll, int rr, int x) 32 { 33 return sum[rr][x] - sum[ll - 1][x]; 34 } 35 void make_p() 36 { 37 register int i,j,k,ans,now; 38 for(i = 1;i <= group;++ i) 39 { 40 ans = 0, now = i; 41 for(int j = l[i];j <= r[i];++ j) ++ sum[i][num[j]]; 42 for(int j = l[i];j <= n;++ j) 43 { 44 ++ c[num[j]]; 45 if(c[num[j]] != 1) 46 { 47 if(c[num[j]] & 1) -- ans; 48 else ++ ans; 49 } 50 if(r[now] == j) p[i][now] = ans, ++ now; 51 } 52 for(int j = l[i];j <= n;++ j) c[num[j]] = 0; 53 } 54 for(i = 2;i <= group;++ i) 55 for(int j = 1;j <= typ;++ j) 56 sum[i][j] += sum[i - 1][j]; 57 } 58 int query(int ll, int rr) 59 { 60 int bl = (ll - 1) / size + 1, br = (rr - 1) / size + 1, ans = 0; 61 if(bl + 2 <= br) 62 { 63 ans = p[bl + 1][br - 1]; 64 for(int i = ll;i <= r[bl];++ i) ++ c[num[i]]; 65 for(int i = l[br];i <= rr;++ i) ++ c[num[i]]; 66 for(int i = ll;i <= r[bl];++ i) 67 if(c[num[i]]) 68 { 69 int tmp = 0; 70 tmp = find(bl + 1, br - 1, num[i]); 71 if((tmp & 1) && (c[num[i]] & 1)) ++ ans; 72 else if(!tmp && !(c[num[i]] & 1)) ++ ans; 73 else if(tmp && !(tmp & 1) && (c[num[i]] & 1)) -- ans; 74 c[num[i]] = 0; 75 } 76 for(int i = l[br];i <= rr;++ i) 77 if(c[num[i]]) 78 { 79 int tmp = 0; 80 tmp = find(bl + 1, br - 1, num[i]); 81 if((tmp & 1) && (c[num[i]] & 1)) ++ ans; 82 else if(!tmp && !(c[num[i]] & 1)) ++ ans; 83 else if(tmp && !(tmp & 1) && (c[num[i]] & 1)) -- ans; 84 c[num[i]] = 0; 85 } 86 } 87 else 88 { 89 for(int j = ll;j <= rr;++ j) 90 { 91 ++ c[num[j]]; 92 if(c[num[j]] == 1) continue; 93 if(c[num[j]] & 1) -- ans; 94 else ++ ans; 95 } 96 for(int j = ll;j <= rr;++ j) c[num[j]] = 0; 97 } 98 return ans; 99 } 100 std::ostringstream os; 101 int main() 102 { 103 read(n), read(typ), read(m); 104 for(register int i = 1;i <= n;++ i) read(num[i]); 105 int M = 1;for(;(1 << M) <= n;++ M);-- M; 106 size = sqrt(n); 107 for(register int i = 1;i <= n;i += size) 108 l[++ group] = i, r[group] = min(i + size - 1, n); 109 make_p(); 110 register int pre = 0, l, r; 111 for(register int i = 1;i <= m;++ i) 112 { 113 read(l), read(r); 114 l = (l + pre), r = (r + pre); 115 if(l >= n) l -= n; 116 if(r >= n) r -= n; 117 l += 1, r += 1; 118 if(l > r) swap(l, r); 119 pre = query(l, r);/*printf("%d", pre);putchar('\n');*/ 120 os << pre << '\n'; 121 } 122 std::cout << os.str(); 123 return 0; 124 } BZOJ2821

?

轉載于:https://www.cnblogs.com/huibixiaoxing/p/8403339.html

總結

以上是生活随笔為你收集整理的BZOJ2821: 作诗(Poetize)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。