开O2可过()
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,q,l,r,a[N],c[N];
inline void read(int &x){
x=0;register char ch=getchar();
while(ch<'0'||ch>'9')ch=getchar();
while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
}
void build(){
for(int i=1,j;i<=n;i++){
c[i]=max(a[i],c[i]),j=i+(i&-i);
if(j<=n)c[j]=max(c[j],c[i]);
}
}
inline int query(int l,int r){
if(r>l)
if(l<r-(r&-r))return max(query(l,r-(r&-r)),c[r]);
else return max(query(l,r-1),a[r]);
return a[l];
}
inline void modify(int x,int v){
for(;x<=n;x+=x&-x)c[x]=c[x]>v?c[x]:v;
}
int main(){
read(n),read(q);
for(int i=1;i<=n;i++)read(a[i]);
build();
while(q--)read(l),read(r),printf("%d\n",query(l,r));
return 0;
}
```
by 0x3ffff @ 2023-10-12 22:01:07
不开O2好像也可以过()
by 0x3ffff @ 2023-10-12 22:03:35
ok
by 403notfound @ 2023-10-13 07:27:22
@[0x3ffff](/user/227252) 什么原理？
by 403notfound @ 2023-10-13 07:40:18
@[0x3ffff](/user/227252) 关注你了
by 403notfound @ 2023-10-13 07:41:52
@[403notfound](/user/891150)
树状数组维护的是(x-lowbit(x),x)这一个区间的最值，我上面query函数是递归写法,你也可以把query写成循环:
```cpp
inline int query(int l, int r) {
int ret=0;
while(r>=l){
ret=max(ret,a[r]),r--;
for(;r-(r&-r)>=l;r-=r&-r)
ret=max(ret,c[r]);
}
return ret;
}
```
by 0x3ffff @ 2023-10-13 08:10:44
@[0x3ffff](/user/227252) 它T了！！！（开力O2）
by 403notfound @ 2023-10-13 11:47:54
[这里](https://www.luogu.com.cn/record/129058347)
by 403notfound @ 2023-10-13 11:49:15
@[403notfound](/user/891150) 我这里可过啊，你贴下代码
by 0x3ffff @ 2023-10-13 13:00:58
```cpp
#include <bits/stdc++.h>
#define ll long long
using namespace std;
inline ll read(){
ll x=0,f=1;
char ch=getchar();
while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
return x*f;
}
ll n , m , a[100005] , c[100005];
ll maxx(ll l , ll r){
if (r > l){
if (l < r - r & -r) return maxx(maxx(l , r - r & -r) , c[r]);
else return max(maxx(l , r - 1) , a[r]);
}
return a[l];
}
int main(){
n = read() , m = read();
for (int i = 1;i <= n;i++) a[i] = read();
for (int i = 1;i <= n;i++){
c[i] = max(c[i] , a[i]);
ll j = i + i & -i;
if (j <= n) c[j] = max(c[j] , c[i]);
}
for (int i = 1 , l , r;i <= n;i++) l = read() , r = read() , printf("%lld\n",maxx(l , r));
return 0;
}
``````
by 403notfound @ 2023-10-13 14:14:21