Posted on 2009-10-06 12:28
hyf 阅读(395)
评论(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 }