题解 P1531 【I Hate It】

这个题是线段树不错，但是树状数组也可以做出来！！ ``` #include<iostream> #include<cstdio> #include<algorithm> #include<cmath> using namespace std; long long n,m,a[200001],d[200001],b,c,ans; char cc; inline void rad(long long &noi) //快读 { bool mark=false; static char ch; while(ch=getchar(),ch<'0'||ch>'9') if(ch=='-') mark=true; noi=ch-'0'; while(ch=getchar(),ch<='9'&&ch>='0') noi=(noi<<3)+(noi<<1)+ch-'0'; if(mark) noi=-noi; } int main() { rad(n);rad(m); for(int i=1;i<=n;i++) { rad(a[i]); //读入学生成绩 for(int j=i;j<=n;j+=(j&(-j))) d[j]=max(d[j],a[i]); //存放最大值 } for(int i=1;i<=m;i++) { cin>>cc; if(cc=='U') //改学生成绩 { rad(b);rad(c);a[b]=max(a[b],c); for(int j=b;j<=n;j+=(j&(-j))) d[j]=max(d[j],c); //修改最大值 } else { rad(b);rad(c);ans=0; //重点！！！！！ while(b<=c) //起点小于终点的时候停止 { while(c-(c&(-c))>=b) //若终点减去lowbit仍然大于起点 { ans=max(ans,d[c]); //更新ans和终点位置 c-=c&(-c); } //做完while，终点减去lowbit小于起点 ans=max(ans,a[c]);c--; //重点！！终点-1，避免减去lowbit小于起点 } printf("%lld\n",ans); } } return 0; } ``` ~~听说有人说树状数组不能修改查询最大值~~ #### **下面我们来模拟一下，假如要求$2-15$之间的最大值。** - $c=15$ - $c=14$ - $c=12$ - $c=8 $ ------------ 此时$while$退出，$c-1=7$ ------------ - $c=7$ - $c=6$ - $c=4$ ------------ 此时$while$退出，$c-1=3$ ------------ - $c=3$ - $c=2$ ------------ #### 结束!! 树状数组跑的还挺快，不加氧气$100ms$，加入氧气氧化$50ms$。希望对大家能有所帮助。