关于信用体系建设的网站,品牌网址,股票软件定制,视频网站怎么做排名题意#xff1a;中文题#xff0c;不多解释 思路#xff1a;这个题原本用线段树很容易做#xff0c;但分块其实也很容易#xff0c;对于分块的复杂度还不是很会计算#xff0c;只知道是每次分为sqrt#xff08;n#xff09;块#xff0c;然后一共有sqrt#xff08;n中文题不多解释 思路这个题原本用线段树很容易做但分块其实也很容易对于分块的复杂度还不是很会计算只知道是每次分为sqrtn块然后一共有sqrtn块其他地方直接暴力这应该是hzw大牛里的第一类最简单的分块跑的好像比线段树慢很多 代码 #include bits/stdc.h
using namespace std;
const int maxn2e57;int n,m;
int block,a[maxn],num[maxn],maxe[maxn];void query(int l,int r)
{int cnt0;for(int il;imin(num[l]*block,r);i){cntmax(cnt,a[i]);
// printf(test %d %d\n,i,a[i1]);}if(num[l]!num[r]){for(int i(num[r]-1)*block1;ir;i){cntmax(cnt,a[i]);}}for(int inum[l]1;inum[r];i){cntmax(cnt,maxe[i]);}printf(%d\n,cnt);
}
void update(int x,int y)
{a[x]y;maxe[num[x]]0;for(int i(num[x]-1)*block1;i(num[x]*block);i){maxe[num[x]]max(maxe[num[x]],a[i]);}
}
int main()
{while(~scanf(%d%d,n,m)){blocksqrt(n);
// memset(a,0,sizeof(a));for(int i1;in;i){scanf(%d,a[i]);
// printf(%d %d\n,i,a[i]);num[i](i-1)/block1;}memset(maxe,0,sizeof(maxe));for(int i1;in;i){maxe[num[i]]max(maxe[num[i]],a[i]);}char ch[5];while(m--){scanf(%s,ch);if(ch[0]Q){int t1,t2;scanf(%d%d,t1,t2);query(t1,t2);}else{int t1,t2;scanf(%d%d,t1,t2);update(t1,t2);}}}return 0;
}
/*
5 6
1 2 3 4 5
Q 1 5
U 3 6
Q 3 4
Q 4 5
U 2 9
Q 1 5
*/ 转载于:https://www.cnblogs.com/lalalatianlalu/p/8582777.html
