像诗一样代码，像云一样生活
概率加DP一直是自己的弱项，于是找了两个这样的题目来做。
http://acm.hdu.edu.cn/showproblem.php?pid=2955
http://acm.hdu.edu.cn/showproblem.php?pid=1203
这两个还都算是比较水的题目，在这提一下就是了。
1203：用f[i][j]表示前i个学校用j万美元申请费，不能获得offer的最小概率，当然f数组是double类型的，则初始化为f[][]=1;状态转移方程为![f[i][j] = min(f[i - 1][j], f[i - 1][j - a[i]] * (1 - p[i]))](/user_files/hustsxh/epics/8a65fa06f4e962ba9c1e71706c01cbe507de0c79.png "f[i][j] = min(f[i - 1][j], f[i - 1][j - a[i]] * (1 - p[i]))")
当然，这个题目用滚动数组会很方便。
2599：网上有人说把概率放大，做为容量，把钱数作为价值来进行背包。我觉得只是不恰当的。这个题目应该把钱数做为容量进行背包：
f[i][j]表示在前i个bank，抢劫j个单位的钱都逃走的最大概率。初始化f[][] = 0, f[0][0] = 1;状态转移方程为
![f[i][j] = max(f[i - 1][j], f[i - 1][j - m[i]] * (1 - p[i]))](/user_files/hustsxh/epics/19919da87e9557d7a7e374fcccbc9ca2115f9858.png "f[i][j] = max(f[i - 1][j], f[i - 1][j - m[i]] * (1 - p[i]))")
同上，这个题目用滚动数组亦比较方便。
http://acm.hdu.edu.cn/showproblem.php?pid=3376
题目大意： 在一个n*n(n <= 600)的方格图中有些1 到100的数，一个人从左上角出发，可以向下走一格，也可以向下走一格，直到走到右下角。然后返回到左上角，返回的时候不能经过走过的位置。走过某一个格子的时候可以取走格子里面的数。求取到数的和最大值。
其实这个题目以前就看过，但是没有认真去想。今天baidu了一下的。得到的基本思路都是差不多的，都是多线程动态规划，这里有这篇比较好的：
http://www.redswallowz.com/bbs/read.php?tid=2827
但我感觉换一种表示状态可能会更好一点。 我用f[x1][y1][x2]来表示状态。f[x1][y1][x2]表示一个线程在点(x1, y1)，另一个在点(x2, x1 + y1 - x2)时，所能获得的最大和。则：
f[1][1][1] = map[1][1];
f[x1][y1][x2] = max{f[x1 - 1][y1][x2 - 1], f[x1 - 1][y1][x2], f[x1][y1 - 1][x2 - 1], f[x1][y1 - 1][x2]} + map[x1][y1] + map[x2][x1 + y1 - x2] | x1 < x2;
这样的循环变量的范围会好控制点。
对于时间复杂度而言虽然都是O(n^3)的，但是后面一种方法常数会稍微的小一点。其实今天rp还算是比较好的。解题报告上说是用网络流（这里就不讨论这种方法，感兴趣的同学自己查资料）ms是O(n^2)的复杂度，但是我用O(n^3)优化了很久（用C++ TLE了，用C AC了）的DP照样过了，这小常数可是功不可没呀！
对于空间复杂度来说，虽然都是O(n^3)，但前面的一种表达的常数是2，这个常数是1。其实就这个题目而言你是非用滚动数组不可的，不然肯定MLE。对于滚动数组，可能有些人不知道，其实很简单。就是我在算f[x1][y1][x2] 的时候只会用到f[x1 - 1][][]和f[x1][][]的数据，f[1 to x1 - 2][][]都是没有用的，这样很自然的就能想到，我用f[2][n][n]来代替f[n][n][n]。我用f[0][][]和f[1][][]交替表示f[x1 - 1][][]和f[x1][][]。这样就能达到将空间复杂度降到O(n^2)。
一下是这种方法的核心代码：
memset(f, 0, sizeof(f));
f[1][1][1] = map[1][1];
now = 1, last = 0;
for(x1 = 2; x1 <= n; ++ x1) {
for(y1 = 1; y1 < n; ++ y1) {
for(x2 = max(1, x1 + y1 - n); x2 < x1; ++ x2) {
f[now][y1][x2] = max(f[last][y1][x2 - 1], f[last][y1][x2], f[now][y1 - 1][x2 - 1], f[now][y1 - 1][x2]) + map[x1][y1] + map[x2][x1 + y1 - x2];
}
}
}
ans = f[n % 2][n - 1][n -1] + a[n][n];
八数码是经典的搜索问题这已经是众所周知的 。
今天一天就做了这一个问题，感觉挺有收获的，于是想写点心得。
先来看下题目：
http://acm.pku.edu.cn/JudgeOnline/problem?id=1077
最先想到的是直接BFS，这也是最简单的想法。但一开始就遇到了一个公共的问题（为什么说是公共的问题呢。因为不管你用什么方式的搜索都会遇到的）——如何判重。最简单的就是直接将棋盘转化成一个9位的十进制数。但这用什么数据结构呢？数组，10^9！这个内存是不允许的；用set，这个时间是不允许的。后面听勇哥说，全排是有完美的hash函数的，于是在网上找到这个——http://bbs3.chinaunix.net/viewthread.php?tid=1283459，这上面解释得很清楚。于是按照上面的hash方法写了个单向的BFS，附：
#include <cstdio>
#include <cstring>
struct node {
int pre; //上一个节点和如何变换的信息
int p; // x即9的下标
char ch[10];//用于记录棋盘信息
}st[400000];
//队列数组 ，9！= 362880
bool vis[400000];//判重数组
int perm[] = {1,1,2,6,24,120,720,5040,40320};//n！
int d[] = { -1 , -3, 1, 3};//四个方向的下标变换
bool move[][4] = {0,0,1,1, 1,0,1,1, 1,0,0,1, 0,1,1,1, 1,1,1,1, 1,1,0,1, 0,1,1,0, 1,1,1,0, 1,1,0,0};
//各个位置的可行变换
int hash(char x[])//用逆序数和变进制进行hash
{
int h = 0;
for(int i = 1;i<9;i++){
int count = 0;
for(int j=0;j<i;j++)
if(x[j] > x[i])count ++;
h += count * perm[i];
}
return h;
}
bool end (char x[])//判断是否到目标状态
{
for(char i = 0;i<9;i++){
if(x[i] != i + '1') return false;
}
return true;
}
int BFS(char *num,int p)
{
int left ,right;
left = right = 1;
memset(vis,0,sizeof(vis));
strcpy(st[right].ch,num);
st[right].p = p;
st[right ++].pre = 0;
vis[hash(st[left].ch)] = 1;
while(left < right){
int p1 ,p2 ;
p1 = st[left].p;
for(int i = 0 ;i<4;i++)if(move[p1][i]){
p2 = st[right].p = p1 + d[i];
strcpy(st[right].ch,st[left].ch);
char tp = st[right].ch[p2] ;
st[right].ch[p2] = st[right].ch[p1] ;
st[right].ch[p1] = tp ;
st[right].pre = left << 2 | i;//将上一个节点的下标和变换规则压进一个数字
if(end(st[right].ch)) return st[right].pre;
int key = hash(st[right].ch);
if( ! vis[key] ) { vis[key] = 1 ; right ++;}
}
left ++;
}
return -1;
}
int main()
{
char num[10] ,der[]="lurd",step[100];
int p ;
for(int i =0 ;i<9;){
num[i] = getchar();
if(num[i] == 'x') { num[i] = '9' ; p = i; }//将x转化成'9'，这样便于hash，和判结束
if(num[i]<='9' && num[i]>='1') i++;
}
num[9] = '\0';
int i = 0;
if(!end(num)){
int k = BFS(num,p);
if( k == -1) printf("unsolvable");
else {
while(k){
step[ ++ i] = der[k&3];
k = st[k>>2].pre;
}
for(;i>0;i--) putchar(step[i]);
puts("");
}
}
return 0;
}
在知道初状态（输入）和末状态（12345678x）的情况下还可以用双向BFS，无论从空间还是从时间的复杂度来说，双向BFS都是比单向BFS都优。单向的BFS的时间和空间都是k^n级的，k是一个状态分支的个数，这里理论是 k = 4，实际上2到3之间，n是迭代的层数，双向BFS的时间和空间的复杂度都是k^(n/2)级的。就是双向BFS的代码复杂度要高一些。在poj上单向BFS是4104K 266MS 2067B，双向BFS是1280K 16MS 2589B
附：双向BFS代码
#include <cstdio>
#include <cstring>
#define M 400000
struct node {
int pre,p；
int key; //这个节点状态对应的hash值
char ch[10];
}st[2][M];
bool vis[2][M];
int perm[] = {1,1,2,6,24,120,720,5040,40320};
int d[] = { -1 , -3, 1, 3};
bool move[][4] = {0,0,1,1, 1,0,1,1, 1,0,0,1, 0,1,1,1, 1,1,1,1, 1,1,0,1, 0,1,1,0, 1,1,1,0, 1,1,0,0};
int hash(char x[])
{
int h = 0;
for(int i = 1;i<9;i++){
int count = 0;
for(int j=0;j<i;j++)
if(x[j] > x[i])count ++;
h += count * perm[i];
}
return h;
}
int BFS(char *num,int p)
{
int l[2] ,r[2] ,key;
l[0] = l[1] = r[0] = r[1] = 1;
memset(vis,0,sizeof(vis));
strcpy(st[0][r[0]].ch,num);
st[0][r[0]].p = p;
st[0][r[0]].pre = 0;
key = hash(st[0][l[0]].ch);
vis[0][key] = 1;
st[0][r[0] ++].key = key;
strcpy(st[1][r[1]].ch,"123456789");
st[1][r[1]].p = 8;
st[1][r[1]].pre = 0;
key = hash(st[1][l[1]].ch);
vis[1][key] = 1;
st[1][r[1] ++].key = key;
while(l[0] < r[0] && l[1]<r[1]){
int p1 ,p2 ,now = (r[0] - l[0] > r[1] - l[1]);//将节点少的一边进行扩展
p1 = st[now][l[now]].p;
for(int i = 0 ;i<4;i++)if(move[p1][i]){
p2 = st[now][r[now]].p = p1 + d[i];
strcpy(st[now][r[now]].ch,st[now][l[now]].ch);
char tp = st[now][r[now]].ch[p2] ;
st[now][r[now]].ch[p2] = st[now][r[now]].ch[p1] ;
st[now][r[now]].ch[p1] = tp ;
st[now][r[now]].pre = l[now] << 2 | i;
key = hash(st[now][r[now]].ch);
st[now][r[now]].key = key;
if( ! vis[now][key] ) { vis[now][key] = 1 ; r[now] ++;}
if( vis[1-now][key]) return key;//检测当前扩展的状态在另一边是否已出现，
}
l[now] ++;
}
return -1;
}
int main()
{
char num[10] ,der[]="lurd",step[100];
int p ;
for(int i =0 ;i<9;){
num[i] = getchar();
if(num[i] == 'x') { num[i] = '9' ; p = i; }
if(num[i]<='9' && num[i]>='1') i++;
}
num[9] = '\0';
int i = 0;
int k = BFS(num,p);
if( k == -1) printf("unsolvable\n");
else {
int p = 1;
while(st[0][p].key != k) p++;
p = st[0][p].pre ;
while(p){
step[ ++ i] = der[p&3];
p = st[0][p>>2].pre;
}
for(;i>0;i--) putchar(step[i]);
p = 1;
while(st[1][p].key != k) p++;
p = st[1][p].pre;
while(p){
putchar(der[((p & 3) + 2)%4]);
p = st[1][p>>2].pre;
}
puts("");
}
return 0;
}
这道题目还可以用A*来写，原来看过这方面的书籍，还没用自己动手写过A*，于是尝试着写了写。这里用搜索树的深度做g(s)，用但前状态各个字符和目标状态这个字符的哈密尔顿距离之和做f(s)，这里做了个比较危险的假设：我把路径压缩在一个long long 中，一个变换只有4种可能，用2个bit就能保存了，大家都知道long long 占64个bit，所以最多可以存32个变化，也就是说，一个long long 只能保存一天短于32的路径（不知道这样描述是否清楚）。我假设，对于任何状态，变到目标状态至多的步数不会超过32步（无解的状态除外），就像3阶魔方被证明20+步一定能被搞定一样，（如果哪个神牛能证明一下就好了……）。
同样这里也贴出代码（就不注释了，如果有没理解的发邮件给我吧，hustsxh@gmail.com）：
#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
struct node {
long long path;
char ch[10];
int g,f,p;
bool operator <(const node & a)const{
return f>a.f || f==a.f && g > a.g;
}
};
bool vis[400000];
int perm[] = {1,1,2,6,24,120,720,5040,40320};
int d[] = { -1 , -3, 1, 3};
bool move[][4] = {0,0,1,1, 1,0,1,1, 1,0,0,1, 0,1,1,1, 1,1,1,1, 1,1,0,1, 0,1,1,0, 1,1,1,0, 1,1,0,0};
int hash(char x[])
{
int h = 0;
for(int i = 1;i<9;i++){
int count = 0;
for(int j=0;j<i;j++)
if(x[j] > x[i])count ++;
h += count * perm[i];
}
return h;
}
bool end (char x[])
{
for(char i = 0;i<9;i++){
if(x[i] != i + '1') return false;
}
return true;
}
int h(char x[])
{
int h = 0;
for(int i=0;i<9;i++){
h += abs( '1' + i -x[i]);
}
return h;
}
int Astar(char num[],int p,long long & path)
{
memset(vis,0,sizeof(vis));
std::priority_queue <node> c;
node start ;
strcpy(start.ch,num);
start.path = 0;
start.p = p;
start.g = 0;
start.f = start.g + h(start.ch);
vis[hash(start.ch)] = 1;
c.push(start);
while(!c.empty()){
node next, pre = c.top();
c.pop();
for(int i = 0;i<4;i++)if(move[pre.p][i]){
next.p = pre.p + d[i];
next.g = pre.g + 1;
strcpy(next.ch,pre.ch);
next.ch[pre.p] = next.ch[next.p];
next.ch[next.p] = '9';
next.path = pre.path<<2 | i;
next.f = h(next.ch) + next.g ;
if(end(next.ch)) { path = next.path ; return next.g;}
int key = hash(next.ch);
if(!vis[key]) { vis[key] = 1; c.push(next); }
}
}
return -1;
}
int main()
{
char num[10] ,der[]="lurd",step[100];
int p ;
for(int i =0 ;i<9;){
num[i] = getchar();
if(num[i] == 'x') { num[i] = '9' ; p = i; }
if(num[i]<='9' && num[i]>='1') i++;
}
num[9] = '\0';
int i = 0;
if(!end(num)){
long long path ;
int k = Astar(num,p,path);
if( k==-1) printf("unsolvable\n");
else {
for(int i = k-1;i>=0;--i) {
step[i] = der[path&3];
path = path >>2;
}
step[k] = '\0';
puts(step);
}
}
return 0;
}
估计是我写得不够优，在poj的的各个参数是1012K 47MS 2459B
从八数码中学到了一个精妙、完美的hash，第一次写双向BFS，第一次写A*，而且交了三份代码三份代码都是1Y的，很hanppy，在此留下一笔，作为成长的痕迹……
原题：
223. Little Kings
time limit per test: 2 sec.
memory limit per test: 65536 KB
input: standard
output: standard
After solving nice problems about bishops and rooks, Petya decided that he would like to learn to play chess. He started to learn the rules and found out that the most important piece in the game is the king.
The king can move to any adjacent cell (there are up to eight such cells). Thus, two kings are in the attacking position, if they are located on the adjacent cells.
Of course, the first thing Petya wants to know is the number of ways one can position k kings on a chessboard of size n × n so that no two of them are in the attacking position. Help him!
Input
The input file contains two integers n (1 ≤ n ≤ 10) and k (0 ≤ k ≤ n2).
Output
Print a line containing the total number of ways one can put the given number of kings on a chessboard of the given size so that no two of them are in attacking positions.
Sample test(s)
Input
Test #1
3 2
Test #2
4 4
Output
Test #1
16
Test #2
79
很显然，这是一道状态压缩DP题。
我的dp数组是f[11][101][1<<10]，f[i][j][k]表示当前是第i行，已经让入j个king，最后一行（第i行）的状态为k，如果k&(1<<p)等于说明第i行第p列放有一个king，否则为没放king。还有两个辅助数组，一个是b[1<<10]，b[i]的值为二进制i中有1的个数，这里可以用lowbit()优化快速求出b[1<<n]数组，这在转移方程中有用；另是t[1<<10][1<<10]，这个数组记录的是可行的转移状态，具体的说，t[i][0] 表示状态i可以转移到其他状态的数目，t[i][1]到t[i][t[i][0]]分别表示着t[i][0]种可转移的状态。总的来说这两个辅助数组时用来加速DP过程的。下面是我的代码，结合代码更容易理解：
#include <cstdio>
#include <cstring>
long long f[11][101][1<<10];
int t[1<<10][1<<10],b[1<<10],n,m;
int lowbit(int x){
return x&(-x);
}
void pretreatment()
{
for(int i=0;i<(1<<n);i++){
int tp = i;
b[i] = 0;
while( tp > 0){
b[i] ++;
tp -= lowbit(tp);
}
}
for(int i=0;i<(1<<n);i++){
t[i][0] = 0;
if( (i<<1) & i) continue;
for(int j=0;j<(1<<n);j++){
if( (j<<1&j)==0 && (i&j)==0 && (i<<1&j)==0 && (j<<1 &i)==0){
t[i][0] ++;
t[i][t[i][0]] = j;
}
}
}
}
int main()
{
while(scanf("%d%d",&n,&m)!=EOF){
pretreatment();
memset(f,0,sizeof(f));
f[0][0][0] = 1;
for(int i =0;i<n;i++)
for(int j=0;j<=m;j++)
for(int k=0;k<(1<<n);k++)if(f[i][j][k])
for(int p =1 ;p <=t[k][0];p++)if(j+b[t[k][p]]<=m)
f[i+1][j+b[t[k][p]]][t[k][p]]+=f[i][j][k];
long long sum = 0;
for(int i=0;i<(1<<n);i++){
sum += f[n][m][i];
}
printf("%lld\n",sum);
}
}
自我感觉着思路没有错，代码写得还比较漂亮，可郁闷的是 wrong answer on test 84，晕死……
开始的时候我把f[][][]数组定义成int，我还以为是int太小了，事实证明当输入是 10 10 时，输出已经是423677826986，这早就超出了int可以表示的范围，于是马上改成long long，满怀激动的心情按了submit，结果还是Wrong answer on test 84 73 ms 12471 kb，崩溃sgu上这到底是什么数据呀，这也太强大了吧！！！sgu果真是大牛、神牛们去的地方，去了练练可以成牛的人呀！！！膜拜一下做sgu的牛们！！！
现在估计是边界数据的问题，今天不早了，也挺纠结了，睡觉去吧，明天再来看看……
Frequent valuesTime
Limit: 2000MS Memory Limit: 65536K
Total Submissions: 3831 Accepted: 1314
Description
You are given a sequence of n integers a1 , a2 , ... , an in non-decreasing order. In addition to that, you are given several queries consisting of indices i and j (1 ≤ i ≤ j ≤ n). For each query, determine the most frequent value among the integers ai , ... , aj.
Input
The input consists of several test cases. Each test case starts with a line containing two integers n and q (1 ≤ n, q ≤ 100000). The next line contains n integers a1 , ... , an (-100000 ≤ ai ≤ 100000, for each i ∈ {1, ..., n}) separated by spaces. You can assume that for each i ∈ {1, ..., n-1}: ai ≤ ai+1. The following q lines contain one query each, consisting of two integers i and j (1 ≤ i ≤ j ≤ n), which indicate the boundary indices for the
query.
The last test case is followed by a line containing a single 0.
Output
For each query, print one line with one integer: The number of occurrences of the most frequent value within the given range.
Sample Input
10 3
-1 -1 1 1 1 1 3 10 10 10
2 3
1 10
5 10
0
Sample Output
1
4
3
Source
Ulm Local 2007
解：
很显然，这题要用离散化，首先将原始数组a[1..n]，变成另外一个数组b[1..k]，b[i]表示a数组中第i种数的个数（显然k<=n），再用一个数组c[1..k]来记录数组b的前i项和，求频率最高数的时候，我们只要理清所要查询的区间中含有多少个完整的b[i]，求出这些b[i]中的最大值，再于两端边界比较，就能得到结果了。
就拿样例来说，这时a[]={0,-1,-1,1,1,1,1,3,10,10,10}，b[]={0,2,4,1,3}，c[]={0,2,6,7,10}，k=4；
当查询5 10时，通过对c数组的查询可以得到有两个完整的b[i]，就是b[3]=1,b[4]=3，这两个中的最大值是3，再处理边界情况，a[5]到a[6]有两个1，比3小，故可得结果为3。
由于本人的语言表达能力有限，下面贴出代码，请结合代码理解：
线段树求最大值法：
#include <cstdio>
#include <algorithm>
#define MAX 100010
#define Max(a,b) (a>b?a:b)
int a[MAX],b[MAX],c[MAX];
typedef struct node {
int i,j,max;
struct node *left,*right;
}segTree;
segTree t[MAX*2];
int used=0;
segTree *creat(int i,int j)
{
if(i>j){
return NULL;
}
segTree *T=&t[used++];
T->i = i , T->j = j;
if(i==j){
T->left = T->right =NULL;
T->max = b[i];
}
else {
T->left = creat(i,(i+j)/2);
T->right = creat((i+j)/2+1,j);
T->max = Max(T->left->max,T->right->max);
}
return T;
}
int search(segTree *T,int i,int j)
{
if(T== NULL || T->i >j || T->j <i){
return 0;
}
if(T->i>=i && T->j<=j){
return T->max;
}
int leftmax = search(T->left,i,j),rightmax = search(T->right,i,j);
return Max(leftmax,rightmax);
}
int main()
{
int n,q,x,y,k;
while(scanf("%d",&n),n>0){
scanf("%d",&q);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
}
b[1]=1,x=a[1],k=1;
for(int i=2;i<=n;i++){
if(x==a[i]){
b[k]++;
}
else {
b[++k]=1;
x=a[i];
}
}
segTree *T=creat(1,k);
c[0]=0;
for(int i=1;i<=k;i++){
c[i]=c[i-1]+b[i];
}
c[++k]=100001;
for(int i=0;i<q;i++){
scanf("%d%d",&x,&y);
int tempi = std::lower_bound(c,c+k+1,x-1) - c +1 ;/*这里处理的一些细节要注意一下*/
int tempj = std::lower_bound(c,c+k+1,y+1) - c- 1;
if(tempi>tempj+1){
printf("%d\n",y-x+1);
}
else if(tempi==tempj+1){
printf("%d\n",Max(c[tempj]-x+1,y-c[tempj]));
}
else {
int max = search(T,tempi,tempj);
max = Max(max,c[tempi-1]-x+1);
max = Max(max,y-c[tempj]);
printf("%d\n",max);
}
}
}
}
很久以前就听说有一个RMQ问题貌似是求区间极大极小值，于是baidu了一下，原来RMQ (Range Minimum/Maximum Query)问题是指：对于长度为n的数列A，回答若干询问RMQ(A,i,j)(i,j<=n)，返回数列A中下标在[i,j]里的最小(大）值。这里有两种较优的方法，一是上面写的线段树求法，二是没学过的动态规划ST算法（Sparse Table）。先简要介绍一下ST算法：以求最大值为例，设d[i,j]表示[i,i+2^j-1]这个区间内的最大值，那么在询问到[a,b]区间的最大值时答案就是max(d[a,k], d[b-2^k+1,k])，其中k是满足2^k<=b-a的最大的k,即k=[ln(b-a+1)/ln(2)]，d的求法可以用动态规划，d[i,j]=max(d[i,j-1],d[i+2^(j-1),j-1])（摘自百度百科）。学习了这种算法以后，就试着用这种方法来解这道题，于是又下面代码：
#include <cstdio>
#include <cmath>
#include <algorithm>
#define MAX 100010
#define Max(a,b) (a>b?a:b)
int a[MAX],b[MAX][20],c[MAX];
void make(int n)
{
int k=(int)(log(n*1.0)/log(2.0));
for(int j=1;j<=k;j++){
for(int i=1;i<=n-(1<<j)+1;i++){
b[i][j]=Max(b[i][j-1],b[i+(1<<(j-1))][j-1]);
}
}
}
int search(int i,int j)
{
int k=(int)(log(j-i+1.0)/log(2.0));
int rmq=Max(b[i][k], b[j - (1 <<k) + 1][k]);
return rmq;
}
int main()
{
int n,q,x,y,k;
while(scanf("%d",&n),n>0){
scanf("%d",&q);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
}
b[1][0]=1,x=a[1],k=1;
for(int i=2;i<=n;i++){
if(x==a[i]){
b[k][0]++;
}
else {
b[++k][0]=1;
x=a[i];
}
}
make(k);
c[0]=0;
for(int i=1;i<=k;i++){
c[i]=c[i-1]+b[i][0];
}
c[++k]=100001;
for(int i=0;i<q;i++){
scanf("%d%d",&x,&y);
int tempi = std::lower_bound(c,c+k+1,x-1) - c +1 ;
int tempj = std::lower_bound(c,c+k+1,y+1) - c- 1;
if(tempi>tempj+1){
printf("%d\n",y-x+1);
}
else if(tempi==tempj+1){
printf("%d\n",Max(c[tempj]-x+1,y-c[tempj]));
}
else {
int max = search(tempi,tempj);
max = Max(max,c[tempi-1]-x+1);
max = Max(max,y-c[tempj]);
printf("%d\n",max);
}
}
}
}
注意，不要把int k=(int)(log(n*1.0)/log(2.0));写成int k=(int)(log(n)/log(2));用G++交不会有事，可用C++交就会
math.h(567): could be 'long double log(long double)'
math.h(519): or 'float log(float)'
math.h(121): or 'double log(double)'
while trying to match the argument list '(int)'
开始没看懂意思，CE了n多次，血的教训呀……
比较两种算法，先从空间复杂度来说，线段树是o(n)的，ST是o(nlogn)，就这点而言线段树要优于ST；
再看预处理，线段树的预处理的o(n)的，而ST的预处理是o(nlogn)的，
而对于一次查询，线段树是o(logn)的，ST更快，是o(1)的，
显然从时间的复杂度来说，他们各有长处，当n远远大于q（查询次数）时，线段树是占优势的，而对于q远远大于n的情况，ST就更占优势了
而对于代码复杂度，ST要优于线段树
由于这题n的范围和p的范围相同，于是两种算法错不多：
线段树：3368 Accepted 2684K 657MS C++ 2054B
ST：3368 Accepted 4224K 532MS C++ 1650B
还有一点不能忘记，线段树是在线的算法，而ST是离线的……