vijos1664 真-资源勘探题解

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

   

Feedback

# re: vijos1664 真-资源勘探题解[未登录]  回复  更多评论   

2009-10-06 21:35 by Tim
orz?
ORZ!

# re: vijos1664 真-资源勘探题解[未登录]  回复  更多评论   

2009-11-27 08:32 by SonicMisora
ORZ!

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理