#include <bits/stdc++.h>
#define ios \
ios::sync_with_stdio(false); \
cin.tie(nullptr); \
cout.tie(nullptr)
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define per(i,a,n) for(int i=n;i>=a;i--)
#define lowbit(x) ((x) & - (x))
#define pb push_back
#define SZ(v) ((int)v.size())
#define PI acos(-1)
#define x first
#define y second
#define mem(a,b) memset((a),(b),sizeof(a))
using namespace std;
typedef long long ll;
const int INF=0x3f3f3f3f;
const ll LLINF=0x3f3f3f3f3f3f3f3fLL;
const double eps=1e-6;
const int MAX=2e5+10;
const ll mod=1e9+7;
/********************************* std-head *********************************/
int gcd(int a, int b){ //最大公约数
return b? gcd(b, a%b):a;
}
int lcm(int a, int b){ //最小公倍数
return a / gcd(a, b) * b;
}
bool isleap(int y) {//判断闰年
return (y % 4 == 0 && y % 100 != 0) || (y % 400 == 0);//闰年可以被4整除但不能被100整除，或能被400整除。
}
bool check(int year, int mouth, int day) {//判断日期是否合法
if (mouth > 12 || mouth == 0)return false;
if (day > 31)return false;
if (mouth == 2) {
if (isleap(year) && day > 29)
return false;
if (!isleap(year) && day > 28)
return false;
}
if (mouth == 4 || mouth == 6 || mouth == 9 || mouth == 11)
if (day > 30)return false;
return true;
}
struct sta {
bool m[n][n];
bool operator<(const sta &rhs) const {
return memcmp(m, rhs.m, sizeof(m)) < 0 ; //便于set去重时的排序
}
};
sta st;
bool dis[n][n];
void ff_(int x, int y) { //检验连通性（原理dfs递归）
dis[x][y] = true;
for (int i = 0; i < 4; ++i) {
int nx = x + dx[i], ny = y + dy[i];
if (nx < 0 || nx > n - 1 || ny < 0 || ny > n - 1) continue;
if (dis[nx][ny] || st.m[nx][ny] != st.m[x][y]) continue; //只填未重复，和颜色相同的块
ff_(nx, ny);
}
}
bool ff() {
memset(dis, 0, sizeof(dis));
int cnt = 0;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j)
if (!dis[i][j]) {
ff_(i, j);
++cnt;
}
}
return cnt == 1; //一块连通区域
}
sort(a.begin(),a.end(),greater<int>());//从大到小排序，输出 8 7 6 5 5 4 3 2
sort(s.begin(),s.end()); //字符串内部排序，得到全排列数列
do{
cout<<s<<endl;
}while(next_permutation(s.begin(),s.end()));
int bin_search(vector<int> &nums,int target)
{
int n = nums.size();
int left = 0;
int right = n - 1; // 定义target在左闭右闭的区间里，[left, right]
while (left <= right) { // 当left==right，区间[left, right]依然有效
int middle = left + ((right - left) / 2);// 防止溢出 等同于(left + right)/2
if (nums[middle] > target) {
right = middle - 1; // target 在左区间，所以[left, middle - 1]
} else if (nums[middle] < target) {
left = middle + 1; // target 在右区间，所以[middle + 1, right]
} else { // nums[middle] == target
return middle;
}
}
// 分别处理如下四种情况
// 目标值在数组所有元素之前 [0, -1]
// 目标值等于数组中某一个元素 return middle;
// 目标值插入数组中的位置 [left, right]，return right + 1
// 目标值在数组所有元素之后的情况 [left, right]， return right + 1
return right + 1;
} //若考虑实数二分，不用考虑整数的取整问题，所以可以直接左右都令为mid
const int maxn = 100001; //倍增法求区间最值
int n,m;
int a[maxn],dp_max[maxn][40]; //dp_min[maxn][40];
void st_init(){
for(int i=1;i<=n;i++) //初始化区间长度为1时的值
dp_max[i][0]=a[i]; //最大值。如果题目求区间最小值就改为dp_min
int p = (int)(log(double(n)) / log(2.0));
//int p=log2(n); //两者写法都行
for(int k=1;k<=p;k++) //倍增计算小区间。先算小区间，再算大区间，逐步递推
for(int s=1;s+(1<<k)<=n+1;s++)
dp_max[s][k]=max(dp_max[s][k-1], dp_max[s+(1<<(k-1))][k-1]);
//最大值。如果题目求区间最小值就改为dp_min、min
}
int st_query(int L,int R){
// int k = log2(R-L+1); //2种方法求k
int k = (int)(log(double(R-L+1)) / log(2.0));
return max(dp_max[L][k],dp_max[R-(1<<k)+1][k]);
//最大值。如果题目求区间最小值就改为dp_min、min
}
int main(){
scanf("%d%d",&n,&m); //n个元素中查询m个区间
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
st_init();
for(int i=1;i<=m;i++){
int L,R;
scanf("%d%d",&L,&R);
printf("%d\n",st_query(L,R));
}
return 0;
}
for(int i = 1; i <= n ; i ++)
sum[i] = sum[i - 1] + a[i];//计算前缀和时数组下标一定要从1开始，方便计算
//常用于需要多次查找某一区间和的问题
void insert(int l,int r,int c) //一维差分处理，相当于给l,r区间每个a[]元素值加c
{
b[l]+=c;
b[r+1]-=c;
}insert(i,i,a[i]);
void insert(int x1,int y1,int x2,int y2,int c) //二维差分处理
{
b[x1][y1]+=c;
b[x1][y2+1]-=c;
b[x2+1][y1]-=c;
b[x2+1][y2+1]+=c;
}insert(i,j,i,j,a[i][j]);
void Merge(ll l, ll mid, ll r){ //归并排序处理逆序对问题
ll i=l, j = mid+1, t=0;
while(i <= mid && j <= r){
if(a[i] > a[j]){
b[t++] = a[j++];
cnt += mid-i+1; //记录逆序对数量
}
else b[t++]=a[i++];
}
//一个子序列中的数都处理完了，另一个还没有，把剩下的直接复制过来：
while(i <= mid) b[t++]=a[i++];
while(j <= r) b[t++]=a[j++];
for(i=0; i<t; i++) a[l+i] = b[i]; //把排好序的b[]复制回a[]
}
void Mergesort(ll l, ll r){
if(l<r){
ll mid = (l+r)/2; //平分成两个子序列
Mergesort(l, mid);
Mergesort(mid+1, r);
Merge(l, mid, r); //合并
}
}
int a[20]={1,2,3,4,5,6,7,8,9,10,11,12,13}; //自写全排列，从小到大生成新的数组b[]
bool vis[20]; //记录第i个数是否用过
int b[20]; //生成的一个全排列
void dfs(int s,int t){
if(s == t) { //递归结束，产生一个全排列
for(int i = 0; i < t; ++i) //输出一个排列
cout << b[i] << " ";
cout<<endl;
return;
}
for(int i=0;i<t;i++)
if(!vis[i]){
vis[i]=true;
b[s]=a[i];
dfs(s+1,t);
vis[i]=false;
}
}
int d[4][2] = {{0,1}, {0,-1}, {1,0}, {-1,0}};
ans; //答案，用全局变量表示
void dfs(层数，其他参数){
if (出局判断){ //到达最底层，或者满足条件退出
更新答案; //答案一般用全局变量表示
return; //返回到上一层
}
(剪枝) //在进一步DFS之前剪枝
for (枚举下一层可能的情况) //对每一个情况继续DFS
if (vis[i] == 0) { //如果状态i没有用过，就可以进入下一层
vis[i] = 1; //标记状态i,表示已经用过，在更底层不能再使用
dfs(层数+1，其他参数); //下一层
vis[i] = 0; //恢复状态，回溯时，不影响上一层对这个状态的使用
}
return; //返回到上一层
}
const int maxn = 8e5+5; //并查集模板，合并集合
int s[maxn];
void init_set(){ //初始化
for(int i = 1; i <= maxn; i++)
s[i] = i;
}
int find_set(int x){
if(x != s[x])
s[x] = find_set(s[x]); //路径压缩
return s[x];
}
void merge_set(int x, int y){ //合并
x = find_set(x);
y = find_set(y);
if(x != y) s[x] = s[y];
}
int tree[N]={0}; //树状数组处理动态区间和
void update(int x, int d) { //修改元素a[x], a[x] = a[x] + d
while(x <= N) {
tree[x] += d;
x += lowbit(x);
}
}
int sum(int x) { //返回前缀和sum = a[1] + a[2] +... + a[x]
int ans = 0;
while(x > 0){
ans += tree[x];
x -= lowbit(x);
}
return ans;
}
long long ans=0;
for(int i=n;i>0;--i){ //倒序处理,计算序列rank[]的逆序对数量
update(Rank[i],1);
ans += sum(Rank[i]-1);
}
//线段树板子，可求区间最值，区间和
const int MAXN = 1e5 + 10;
ll a[MAXN]; //记录数列的元素，从a[1]开始
ll tree[MAXN<<2];//tree[i]：第i个结点的值，表示一个线段区间的值，例如最值、区间和
ll tag[MAXN<<2]; //tag[i]：第i个结点的lazy-tag，统一记录这个区间的修改
ll ls(ll x){ return x<<1; } //定位左儿子：x*2
ll rs(ll x){ return x<<1|1;} //定位右儿子：x*2 + 1
void push_up(ll p){ //从下往上传递区间值
tree[p] = tree[ls(p)] + tree[rs(p)];
//本题是区间和。如果求最小值，改为：tree[p] = min(tree[ls(p)], tree[rs(p)]);
}
void build(ll p,ll pl,ll pr){ //建树。p是结点编号，它指向区间[pl, pr]
tag[p] = 0; //lazy-tag标记
if(pl==pr){tree[p]=a[pl]; return;} //最底层的叶子，赋值
ll mid = (pl+pr) >> 1; //分治：折半
build(ls(p),pl,mid); //左儿子
build(rs(p),mid+1,pr); //右儿子
push_up(p); //从下往上传递区间值
}
void addtag(ll p,ll pl,ll pr,ll d){ //给结点p打tag标记，并更新tree
tag[p] += d; //打上tag标记
tree[p] += d*(pr-pl+1); //计算新的tree
}
void push_down(ll p,ll pl,ll pr){ //不能覆盖时，把tag传给子树
if(tag[p]){ //有tag标记，这是以前做区间修改时留下的
ll mid = (pl+pr)>>1;
addtag(ls(p),pl,mid,tag[p]); //把tag标记传给左子树
addtag(rs(p),mid+1,pr,tag[p]); //把tag标记传给右子树
tag[p]=0; //p自己的tag被传走了，归0
}
}
void update(ll L,ll R,ll p,ll pl,ll pr,ll d){ //区间修改：把[L, R]内每个元素加上d
if(L<=pl && pr<=R){ //完全覆盖，直接返回这个结点，它的子树不用再深入了
addtag(p, pl, pr,d); //给结点p打tag标记，下一次区间修改到p这个结点时会用到
return;
}
push_down(p,pl,pr); //如果不能覆盖，把tag传给子树
ll mid=(pl+pr)>>1;
if(L<=mid) update(L,R,ls(p),pl,mid,d); //递归左子树
if(R>mid) update(L,R,rs(p),mid+1,pr,d); //递归右子树
push_up(p); //更新
}
ll query(ll L,ll R,ll p,ll pl,ll pr){
//查询区间[L,R]；p是当前结点（线段）的编号，[pl,pr]是结点p表示的线段区间
if(pl>=L && R >= pr) return tree[p]; //完全覆盖，直接返回
push_down(p,pl,pr); //不能覆盖，递归子树
ll res=0;
ll mid = (pl+pr)>>1;
if(L<=mid) res+=query(L,R,ls(p),pl,mid); //左子结点有重叠
if(R>mid) res+=query(L,R,rs(p),mid+1,pr); //右子结点有重叠
return res;
}
ll n, m; scanf("%lld%lld",&n,&m); //n个点，m个操作
for(ll i=1;i<=n;i++) scanf("%lld",&a[i]);
build(1,1,n); //建树
while(m--){
ll q,L,R,d;
scanf("%lld",&q);
if (q==1){ //区间修改：把[L,R]的每个元素加上d
scanf("%lld%lld%lld",&L,&R,&d);
update(L,R,1,1,n,d);
}
else { //区间询问：[L,R]的区间和
scanf("%lld%lld",&L,&R);
printf("%lld\n",query(L,R,1,1,n));
}
}
//计算几何
struct Point{ //点的表示
double x,y;
Point(){}
Point(double x,double y):x(x),y(y){}
Point operator - (Point B){return Point(x-B.x,y-B.y);} //定义减法
};
double Dist(Point A,Point B){ //两点间距离公式
return sqrt((A.x-B.x)*(A.x-B.x) + (A.y-B.y)*(A.y-B.y));
}
typedef Point Vector; //表示向量
double Dot(Vector A,Vector B){return A.x*B.x + A.y*B.y;} //求向量A与向量B的点积
double Len(Vector A){return sqrt(Dot(A,A));} // 求向量A的长度
double Angle(Vector A,Vector B){ // 求向量A和向量B的夹角大小
return acos(Dot(A,B)/Len(A)/Len(B));
}
double Cross(Vector A,Vector B){return A.x*B.y – A.y*B.x;} // 求向量A与向量B的叉积
double Area2(Point A,Point B,Point C){
return Cross(B-A, C-A); //计算向量AB与向量AC构成的平行四边形的面积
}
Vector Rotate(Vector A, double rad){ //使向量A逆时针旋转rad度，得到的新向量
return Vector(A.x*cos(rad)-A.y*sin(rad), A.x*sin(rad)+A.y*cos(rad));
}
bool Parallel(Vector A, Vector B){ // 用叉积检查两个向量是否平行或重合
return sgn(Cross(A,B)) == 0;
}
// 点和线的关系
struct Line{
Point p1,p2; //线上的两个点
Line(){}
Line(Point p1,Point p2):p1(p1),p2(p2){}
//根据一个点和倾斜角 angle 确定直线,0<=angle<pi
Line(Point p,double angle){
p1 = p;
if(sgn(angle – pi/2) == 0){p2 = (p1 + Point(0,1));}
else{p2 = (p1 + Point(1,tan(angle)));}
}
//ax+by+c=0
Line(double a,double b,double c){
if(sgn(a) == 0){
p1 = Point(0,-c/b);
p2 = Point(1,-c/b);
}
else if(sgn(b) == 0){
p1 = Point(-c/a,0);
p2 = Point(-c/a,1);
}
else{
p1 = Point(0,-c/b);
p2 = Point(1,(-c-a)/b);
}
}
};
int Point_line_relation(Point p, Line v){ //判断点p与线v的位置关系
int c = sgn(Cross(p-v.p1,v.p2-v.p1));
if(c < 0) return 1; //1：p在v的左边
if(c > 0) return 2; //2：p在v的右边
return 0; //0：p在v上
}
bool Point_on_seg(Point p, Line v){ //点和线段：0 点不在线段v上；1 点在线段v上
return sgn(Cross(p-v.p1, v.p2-v.p1)) == 0 && sgn(Dot(p – v.p1,p- v.p2)) <= 0;
}
double Dis_point_line(Point p, Line v){ //点到直线的距离公式
return fabs(Cross(p-v.p1,v.p2-v.p1))/Distance(v.p1,v.p2);
}
//点在直线上的投影
Point Point_line_proj(Point p, Line v){
double k=Dot(v.p2-v.p1,p-v.p1)/Len2(v.p2-v.p1);
return v.p1+(v.p2-v.p1)*k;
}
//获取点关于直线的对称点
Point Point_line_symmetry(Point p, Line v){
Point q = Point_line_proj(p,v);
return Point(2*q.x-p.x,2*q.y-p.y);
}
int Line_relation(Line v1, Line v2){ //判断两条直线的位置关系
if(sgn(Cross(v1.p2-v1.p1,v2.p2-v2.p1)) == 0){
if(Point_line_relation(v1.p1,v2)==0) return 1; //1 重合
else return 0; //0 平行
}
return 2; //2 相交
}
//判断两条直线是否相交
bool Cross_segment(Point a,Point b,Point c,Point d){//Line1:ab, Line2:cd
double c1=Cross(b-a,c-a),c2=Cross(b-a,d-a);
double d1=Cross(d-c,a-c),d2=Cross(d-c,b-c);
return sgn(c1)*sgn(c2)<=0 && sgn(d1)*sgn(d2)<=0; //1相交；0不相交
}
ll fastPow(ll a, ll n, ll mod){ //快速幂取模
ll ans = 1;
a %= mod; //重要，防止下面的ans*a越界
while(n) {
if(n & 1) ans = (ans*a) % mod; //取模
a = (a*a) % mod; //取模
n >>= 1;
}
return ans;
}
//矩阵快速幂
struct matrix{ int m[N][N]; }; //定义矩阵，常数N是矩阵的行数和列数
matrix operator * (const matrix& a, const matrix& b){
//重载*为矩阵乘法。注意const
matrix c;
memset(c.m, 0, sizeof(c.m)); //清零
for(int i=0; i<N; i++)
for(int j=0; j<N; j++)
for(int k = 0; k<N; k++)
//c.m[i][j] += a.m[i][k] * b.m[k][j]; //不取模
c.m[i][j] = (c.m[i][j] + a.m[i][k] * b.m[k][j]) % mod;//取模
return c;
}
matrix pow_matrix(matrix a, int n){ //矩阵快速幂，代码和普通快速幂几乎一样
matrix ans;
memset(ans.m,0,sizeof(ans.m));
for(int i=0;i<N;i++)
ans.m[i][i] = 1; //初始化为单位矩阵，类似普通快速幂的ans=1
while(n) {
if(n&1) ans = ans * a; //不能简写为ans *= a，这里的*重载了
a = a * a;
n>>=1;
}
return ans;
}
bool is_prime(long long n){ //试除法判断素数
if(n <= 1) return false; //1不是素数
for(long long i=2; i*i <= n; i++)
//或者这样写：i <= sqrt(n)，总计算量更少
if(n % i == 0) return false; //能整除，不是素数
return true; //读者思考，n=2时返回true吗？
}
//埃式筛：
const int MAXN = 1e7; //定义空间大小，1e7约10M
int prime[MAXN+1]; //存放素数，它记录visit[i] = false的项
bool visit[MAXN+1]; //true表示被筛掉，不是素数
int E_sieve(int n) {
for(int i = 0; i <= n; i++) visit[i]= false;
for(int i = 2; i*i <= n; i++) //改为i<=sqrt(n)，循环计算更快
if(!visit[i])
for(int j=i*i; j<=n; j+=i)
visit[j] = true; //j不是素数
//下面记录素数
int k=0; //统计素数个数
for(int i = 2; i <= n; i++)
if(!visit[i])
prime[k++] = i; //存储素数
return k;
}
//区间素数（两重埃式筛）
ll seg_sieve(ll a,ll b) {
for(ll i=0;i*i<=b;++i) vis[i]=true;
for(ll i=0;i<=b-a;++i) seg_prime[i]=true;
for(ll i=2;i*i<=b;++i)
if(vis[i]) { //i是素数
for(ll j=i*i;j*j<=b;j+=i)//筛选[2,sqrt(b)]内的素数
vis[j] = false;
for(ll j=max(2LL,(a+i-1)/i)*i;j<=b;j+=i)//筛选[a,b]内的素数
seg_prime[j-a] = false;
}
ll num=0;
for(ll i=0;i<=b-a;++i) //统计[a,b]内素数个数
if(seg_prime[i])
prime[num++]=i+a; //存[a,b]内的素数
return num;
}
//试除法求一个数的质因子
int p[20]; //p[]记录因子，p[1]是最小因子。一个int数的质因子最多有10几个
int c[40]; //c[i]记录第i个因子的个数。一个因子的个数最多有30几个
int factor(int n){
int m = 0;
for(int i = 2; i <= sqrt(n); i++)
if(n%i == 0){
p[++m] = i, c[m] = 0;
while(n%i == 0) //把n中重复的因子去掉
n/=i, c[m]++;
}
if(n>1) //n没有被除尽，是素数
p[++m] = n, c[m] = 1;
return m; //共m个因子
}
//计算组合数
ll C(int n,int m) { //计算组合数n中取m
if(n==m||m==0) return 1;
else if(n<m) return 0;
else{
ll res=1; //防止溢出，边乘边除，先乘值小的
n=n-m+1;
for(int i=1;i<=m;i++){
res*=n++;
res/=i;
}
return res;
}
}
int dfs(int n,int m){ //dfs递归计算
if(!m) return c[n][m]=true;
if(m==1) return c[n][m]=n;
if(c[n][m]) return c[n][m];
if(n-m<m )m=n-m;
return c[n][m]=(dfs(n-1,m)+dfs(n-1,m-1))%mod;
}
//邻接表
struct edge{
int from,to,w;
edge(int a,int b,int c){form=a;to=b;w=c;}
};
vector<edge> e[NUM]; //e[i]:存第i个结点连接的所有边
for(int i=1;i<=n;i++)
e[i].clear();
e[a].push_back(edge(a,b,c)); //把边（a,b）存到结点a的邻接表中
for(int i=0;i<e[u].size();i++){ //检索结点u的所有邻居
...
}
//Floyd算法计算（计算所有点对之间的最短路，可重复走） n<300;
for(int k=1; k<=n; k++) //floyd的三重循环
for(int i=1; i<=n; i++)
for(int j=1; j<=n; j++) // k循环在i、j循环外面
dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]); //比较：不经过k、经过k
//C++字符串函数
#include<bits/stdc++.h>
using namespace std;
int main(){
string str ="123456789abcdefghiaklmn";
for(int i=0;i<10;i++) //把str看成一个字符串数组
cout<<str[i]<<" ";
cout << endl;
//find函数
cout<<"123的位置: "<<str.find("123")<<endl;
//输出：123的位置: 0
cout<<"34在str[2]到str[n-1]中的位置: "<<str.find("34",2)<<endl;
//输出：34在str[2]到str[n-1]中的位置: 2
cout<<"ab在str[0]到str[12]中的位置: "<<str.rfind("ab",12)<<endl;
//输出：ab在str[0]到str[12]中的位置: 9
//substr()函数
cout<<"str[3]及以后的子串:"<<str.substr(3)<<endl;
//输出：str[3]及以后的子串:456789abcdefghijklmn
//若小于限制长度则报错
cout<<"从str[2]开始的4个字符:"<<str.substr(2,4)<<endl;
//输出：从str[2]开始的4个字符:3456
//find()函数
str.replace(str.find("a"), 5, "@#");
cout<<str<<endl;
//输出：123456789@#fghiaklmn
//insert()函数
str.insert(2, "***");
cout<<"从2号位置插入: "<<str<<endl;
//输出：12***3456789@#fghiaklmn
//添加字符串：append()函数
str.append("$$$");
cout<<"在字符串str后面添加字符串:"<<str<<endl;
//输出： 12***3456789@#fghiaklmn$$$
//字符串长度
cout<<str.size()<<endl;
cout<<str.length()<<endl;
//交换字符串：swap()函数
string str1="aaa",str2="bbb";
swap(str1, str2);
cout<<str1<<" "<<str2<<endl;
//字符串比较函数：compare()，相等输出0，不等输出1
cout<<str1.compare(str2)<<endl;
if(str1==str2) cout <<"=="; //直接比较也行
if(str1!=str2) cout <<"!=";
return 0;
}
京公网安备 11010502036488号