玲珑杯1129-喵哈哈村的战斗魔法师丶坏坏い月

DESCRIPTION

坏坏い月是月大叔的ID，他是一个掌握者772002种魔法的物理系战士，最擅长的技能就是搞事。今天他又要开始搞事了。

给你$n$个数，你需要实现一下操作：

l r v ,在[l,r]区间内找到第一个大于等于v的数,输出这个数的下标,如果找不到的话，请输出-1噢

l r v，让[l,r]区间所有数增加v

INPUT 输入第一行包含一个正整数 $t(1\le t\le 100)$ ,表示有t组数据对于每组数据：第一行包含两个整数 $n(1\le n\le 100000)$, $q(1\le q\le 100000)$,表示数的个数，以及询问的个数。第二行包含 $n$个整数 $a_i(1\le a_i\le 1000000000)$接下来q行，每行四个整数 $opt(1\le opt\le 2),l,r(1\le l\le r\le n),v(1\le v\le 1000000000)$ OUTPUT 对于每个询问，输出一行表示答案. SAMPLE INPUT 1 5 3 1 2 3 4 5 1 1 2 3 2 1 2 3 1 1 2 3 SAMPLE OUTPUT -11 这是一道线段树区间更新并维护最大值的线段树模板题，建树，更新只要照模板敲好，在每次询问的时候优先搜索左区间，注意搜索左边的时候，当前左子树的根保存的最大值并不一定在我们要查的【left,right】的区间就行了，代码里有注释。这里就不累赘了

#include <iostream> #include <stdio.h> #include <string.h> #include <algorithm> #define siz 100005 #define LL long long #define lson(x) ((x)<<1) #define rson(x) (((x)<<1)|1) using namespace std; struct node{ LL mx,addmark; }; LL arr[siz]; node S[siz<<2]; int n,q; LL max(LL a,LL b){ if(a>b) return a; else return b; } void build(int root,int left,int right){ if(left==right){ S[root].mx=arr[left]; S[root].addmark=0; return ; } int mid=(left+right)>>1; build(lson(root),left,mid); build(rson(root),mid+1,right); S[root].mx=max(S[lson(root)].mx,S[rson(root)].mx); S[root].addmark=0; } void pushdown(int root){ if(S[root].addmark!=0){ S[lson(root)].addmark+=S[root].addmark; S[rson(root)].addmark+=S[root].addmark; S[lson(root)].mx+=S[root].addmark; S[rson(root)].mx+=S[root].addmark; S[root].addmark=0; } } void updata(int root,int left,int right,int l,int r,int v){ if(left==l&&r==right){ S[root].addmark+=v; S[root].mx+=v; return ; } pushdown(root); int mid=(left+right)>>1; if(r<=mid) updata(lson(root),left,mid,l,r,v); else if(l>mid){ updata(rson(root),mid+1,right,l,r,v); } else{ updata(lson(root),left,mid,l,mid,v); updata(rson(root),mid+1,right,mid+1,r,v); } S[root].mx=max(S[lson(root)].mx,S[rson(root)].mx); } int flag=0,ans; void query(int root,int left,int right,int l,int r,int v){ if(flag) return ; if(S[root].mx<v){ flag=1; ans=-1; return ; } if(left==right){ if(S[root].mx>=v){ flag=1; ans=left; return ; } else{ flag=1; ans=-1; return ; } } pushdown(root); int mid=(left+right)>>1; if(r<=mid){ query(lson(root),left,mid,l,r,v); } else if(l>mid){ query(rson(root),mid+1,right,l,r,v); } else{ //if(left==l&&S[lson(root)].mx>=v){///不能这样去递归，因为lson(root)的区间是大于等于[left,right]的， ///这就意味着S[losn(root)].mx不一定在[left,right]里面 query(lson(root),left,mid,l,mid,v);///优先询问左子树 if(ans!=-1) return ;///如果左子树找到了大于等于v的，它一定是最左的 else{///否则，标记清零，再去寻找右子树。 flag=0; } query(rson(root),mid+1,right,mid+1,r,v); } } ///以下询问是别人的代码，可供参考 int query1(int root,int left,int right,int l,int r,int v){ if(S[root].mx<v) return -1; if(l<=left&&r>=right){ if(left==right) return left; int mid=(left+right)>>1; pushdown(root); if(S[lson(root)].mx>=v){ return query1(lson(root),left,mid,l,r,v); } else{ return query1(rson(root),mid+1,right,l,r,v); } } else{ pushdown(root); int mid=(left+right)>>1; int res; if(l<=mid){ res=query1(lson(root),left,mid,l,r,v); if(res<=r&&res!=-1) return res; } if(r>mid){ res=query1(rson(root),mid+1,right,l,r,v); if(res<=r&&res!=-1) return res; } } return -1; } void solve(){ build(1,1,n); int opt,l,r,v; while(q--){ flag=0,ans=-1; scanf("%d %d %d %d",&opt,&l,&r,&v); if(opt==1){ query(1,1,n,l,r,v); printf("%d\n",ans); // printf("%d\n",query1(1,1,n,l,r,v)); }else{ updata(1,1,n,l,r,v); } } } int main() { int t; scanf("%d",&t); while(t--){ scanf("%d%d",&n,&q); for(int i=1;i<=n;i++){ scanf("%lld",&arr[i]); } solve(); } return 0; }