hdoj 1754 I hate it

2015-12-15 · 2 min read · 分块数据结构

http://acm.hdu.edu.cn/showproblem.php?pid=1754 题意：给定一个区间，有m组操作，操作可以是改变单点，或者查询区间最大值。对于每组查询，输出。思路：分块。这篇博客说得很不错。http://www.cnblogs.com/sweetsc/archive/2012/08/15/2639395.html

/* ***********************************************
Author :111qqz
Created Time :2015年12月15日 星期二 11时25分17秒
File Name :code/hdu/1754.cpp
************************************************ */

 1#include <cstdio>
 2#include <cstring>
 3#include <iostream>
 4#include <algorithm>
 5#include <vector>
 6#include <queue>
 7#include <set>
 8#include <map>
 9#include <string>
10#include <cmath>
11#include <cstdlib>
12#include <ctime>
13#define fst first
14#define sec second
15#define lson l,m,rt<<1
16#define rson m+1,r,rt<<1|1
17#define ms(a,x) memset(a,x,sizeof(a))
18typedef long long LL;
19#define pi pair < int ,int >
20#define MP make_pair

 1using namespace std;
 2const double eps = 1E-8;
 3const int dx4[4]={1,0,0,-1};
 4const int dy4[4]={0,-1,1,0};
 5const int inf = 0x3f3f3f3f;
 6const int N=2E5+7;
 7int a[N];
 8int mx[N];
 9int n ,m;
10int magic;

 1void pre()
 2{
 3    magic = int(sqrt(n));
 4    ms(mx,-1); //把i%magic去掉试试。
 5    for ( int i = 0 ; i <n ; i++ )  //从0开始比较方便。
 6    {
 7//	if (a[i]>mx[i/magic])
 8//	    mx[i/magic] = a[i];
 9	mx[i/magic] = max(mx[i/magic],a[i]);
10    }

 1int query( int l,int r)
 2{
 3    int ret = a[l];
 4    for ( int j = l ; j <= r;)
 5    {
 6	if (j%magic==0&&j+magic-1<=r)
 7	{
 8	    ret = max(ret,mx[j/magic]);
 9	 //   if (mx[j/magic]>ret) ret= mx[j/magic];
10	    j+= magic;
11	}
12	else  //首尾两段不够magic的部分直接暴力
13	{
14	    ret = max(a[j],ret);
15	    //if (a[j]>ret) ret = a[j];
16	    j++;
17	}
18    }
19    return ret;
20}

 1void update( int x,int delta)
 2{
 3    a[x] = delta;
 4    int l = x/magic*magic;
 5    int r = l+magic;  //找到x对应的哪个块。
 6    for ( int i = l ; i < r ; i++)
 7    {
 8	//	if (i%magic==0||a[i]>mx[i/magic]) mx[i/magic] = a[i];
 9	    mx[i/magic] = max(mx[i/magic],a[i]);
10    }
11}

1int main()
2{
3	#ifndef  ONLINE_JUDGE 
4	freopen("code/in.txt","r",stdin);
5  #endif

 1	while (scanf("%d%d",&n,&m)!=EOF)
 2	{
 3//	    ms(a,0);
 4//	    ms(mx,0);
 5	    for ( int i = 0 ; i < n ; i++) scanf("%d",&a[i]);
 6	    getchar();
 7	    pre();
 8	    while (m--)
 9	    {
10		char opt;
11		scanf("%c ",&opt);
12		if (opt=='Q')
13		{
14		    int l,r;
15		    scanf("%d%d",&l,&r);
16		    getchar();
17		    printf("%d\n",query(l-1,r-1));
18		}
19		else
20		{
21		    int x,delta;
22		    scanf("%d%d",&x,&delta);
23		    getchar(); //又忘记读掉回车符了.....
24		    update(x-1,delta);
25		}
26	    }

1  #ifndef ONLINE_JUDGE  
2  fclose(stdin);
3  #endif
4    return 0;
5}