玲珑oj 1129 ST

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

Time Limit：3s Memory Limit：256MByte

Submissions：490Solved：107

DESCRIPTION

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

给你n

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

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

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

INPUT

输入第一行包含一个正整数t(1≤t≤100)

,表示有t组数据 对于每组数据： 第一行包含两个整数n(1≤n≤100000),q(1≤q≤100000),表示数的个数，以及询问的个数。 第二行包含n个整数 ai(1≤ai≤1000000000) 接下来q行，每行四个整数opt(1≤opt≤2),l,r(1≤l≤r≤n),v(1≤v≤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

-1 1

SOLUTION

“玲珑杯”线上赛 Round #15 河南专场

线段树区间修改，用lazy标记处理，由于我在ask()函数写的不是进行的二分查找而是两边都查找导致TLE，后来改了才AC，可见细节的重要性，

如果在左边找到了满足条件的数则可以放弃右边的查找否则两边都要找。

 #include<bits/stdc++.h>
 using namespace std;
 #define LL long long
 #define MAXN ((100000<<2)+15)
 struct SegTree
 {
     #define lc (id<<1)
     #define rc (id<<1|1)
     #define M  ((L+R)>>1)
     LL Max[MAXN],Add[MAXN];
     void init()
     {
         memset(Max,,sizeof(Max));
         memset(Add,,sizeof(Add));
     }
     void pushdown(int L,int R,int id)
     {
         if(!Add[id]) return;
         Add[lc]+=Add[id];
         Add[rc]+=Add[id];
         Max[lc]+=Add[id];
         Max[rc]+=Add[id];
         Add[id]=;
     }
     void build(int L,int R,int id)
     {
         if(L==R){scanf("%lld",&Max[id]);return;}
         build(L,M,lc);
         build(M+,R,rc);
         Max[id]=max(Max[lc],Max[rc]);
     }
     void update(int L,int R,int id,int l,int r,int v)
     {
         if(L>=l&&R<=r){
             Max[id]+=v;
             Add[id]+=v;
             return;
         }
         pushdown(L,R,id);
         if(l<=M) update(L,M,lc,l,r,v);
         if(r>M)  update(M+,R,rc,l,r,v);
         Max[id]=max(Max[lc],Max[rc]);
     }
     int ask(int L,int R,int id,int l,int r,int v)
     {
         if(Max[id]<v) return -;
         if(L==R){
             if(!(L>=l&&R<=r)) return -;
             if(Max[id]<v) return -;
             else return L;
         }
         pushdown(L,R,id);
         Max[id]=max(Max[lc],Max[rc]);
         int ans=-,y=-;
         if(l<=M) ans=ask(L,M,lc,l,r,v);
         if(ans!=-) return ans;
         if(r>M) y=ask(M+,R,rc,l,r,v);
         return y;
     }
 }seg;
 int main()
 {
     int t,n,m,i,j,k,opt,l,r,v;
     scanf("%d",&t);
     while(t--){
         scanf("%d%d",&n,&m);
         seg.init();
         seg.build(,n,);
         while(m--){
             scanf("%d%d%d%d",&opt,&l,&r,&v);
             if(opt==){
                 printf("%d\n",seg.ask(,n,,l,r,v));
             }
             else{
                 seg.update(,n,,l,r,v);
             }
         }
     }
     return ;
 }