Posted on 2009-10-06 12:28
hyf 閱讀(427)
評論(2) 編輯 收藏 引用 所屬分類:
OI
這是道怨念題，交了5次都等不到puppy，更詭異的是vj上顯示的是ac……
題目的大意是給出n*m的矩陣，詢問(1,1)->(x,y)的子矩陣中只出現一次的元素個數
對于第i行來說，記錄1->i行內元素x最小和次小的橫坐標x0、x1，那么在該行內將元素x記錄進去的子矩陣只能是左下坐標在x0到(x1-1)之間的。
所以按行i掃描，維護(1,1)->(i,x)子矩陣的稀有資源個數,也就是對于在本行內出現的元素算出其新的區間[x0,x1),原區間全部減1，新區間加1，在該行沒有出現的元素不變。
區間整體修改可以用線段樹來維護，但是此題用線段樹T的可能性相當大，注意到這里是維護區間詢問點，所以可以把樹狀數組逆向運用，這樣常數大大降低。
最終復雜度是O(n^2logn)，C++還要進行輸入優化。
囧代碼：
1 #include <iostream>
2 using namespace std;
3 #define LOWBIT(x) (x&(-x))
4
5 int n,m;
6 int data[1100][1100];
7 int r[2000000];
8 int pre[2000000][2];
9 int hash[2000000][2] = {0};
10 int ans = 0;
11 int A[1101] = {0};
12 char s[10000];
13
14 void Modify(int x, int c)
15 {
16 while(x)
17 {
18 A[x] += c;
19 x -= LOWBIT(x);
20 }
21 }
22
23 int Get(int x)
24 {
25 int ans = 0;
26 while(x<=m)
27 {
28 ans += A[x];
29 x += LOWBIT(x);
30 }
31 return ans;
32 }
33
34 void init()
35 {
36 int tmp, p;
37 char *ptr;
38 scanf("%d %d\n",&n,&m);
39 for(int i = 0; i < n; i++)
40 {
41 gets(s);
42 p = tmp = 0;
43 ptr = s;
44 while(*ptr)
45 {
46 if((*ptr)==' ')
47 data[i][p++] = tmp, tmp = 0;
48 else
49 tmp *= 10, tmp += (*ptr)-'0';
50 ptr++;
51 }
52 data[i][p] = tmp;
53 }
54 for(int i = 0; i <= n*m; i++)
55 hash[i][0] = hash[i][1] = m, pre[i][0] = pre[i][1] = m, r[i] = -1;
56 }
57
58 void solve()
59 {
60 int tmp = 0;
61 for(int i = 0; i < n; i++)
62 {
63 for(int j = 0; j < m; j++)
64 {
65 tmp = data[i][j];
66 pre[tmp][0] = hash[tmp][0], pre[tmp][1] = hash[tmp][1];
67 }
68 for(int j = 0; j < m; j++)
69 {
70 tmp = data[i][j];
71 if(j<pre[tmp][0])
72 pre[tmp][1] = pre[tmp][0], pre[tmp][0] = j;
73 else if(j<pre[tmp][1])
74 pre[tmp][1] = j;
75 }
76 for(int j = 0; j < m; j++)
77 {
78 tmp = data[i][j];
79 if(r[tmp]!=i)
80 {
81 Modify(hash[tmp][1],-1);
82 Modify(hash[tmp][0],1);
83 Modify(pre[tmp][1],1);
84 Modify(pre[tmp][0],-1);
85 hash[tmp][0] = pre[tmp][0], hash[tmp][1] = pre[tmp][1];
86 r[tmp] = i;
87 }
88 }
89 for(int j = 1; j <= m; j++)
90 tmp = Get(j), ans ^= tmp;
91 }
92 }
93
94 void print()
95 {
96 printf("%d\n",ans);
97 }
98
99 int main(void)
100 {
101 init();
102 solve();
103 print();
104 return 0;
105 }