记录编号	378146	评测结果	AAAAAAAAAA
题目名称	地震	最终得分	100
用户昵称	sxysxy	是否通过	通过
代码语言	C++	运行时间	2.804 s
提交时间	2017-03-03 10:02:51	内存使用	1.32 MiB

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>
#include <ctime>
#include <list>
#include <cctype>
using namespace std;
#define BETTER_CODE __attribute__ ((optimize("O3"))) 
typedef long long LL;
namespace IO{
  char buf[1<<18], *fs, *ft;
  inline char readc(){
    return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<18,stdin)),fs==ft)?EOF:*fs++;
  }
  BETTER_CODE
  inline int readint(){
    char c; int r;
    while(c = readc()){if(c >= '0' && c <= '9'){r = c^0x30;break;}}
    while(isdigit(c = readc()))r = (r<<3)+(r<<1)+(c^0x30);
    return r;
  }
  BETTER_CODE
  inline LL readll(){
    char c; LL r;
    bool s = false;
    while(c = readc()){
      if(c >= '0' && c <= '9'){
        r = c^0x30;break;
      }else if(c == '-')s = true;
    }
    while(isdigit(c = readc()))r = (r<<3)+(r<<1)+(c^0x30);
    return s?-r:r;
  }
  inline int read_string(char *str){
    int len = 1;char c;
    while(!isalpha(c = readc()));str[0] = c;
    while(isalpha(c = readc()))str[len++] = c;
    str[len] = 0;
    return len;
  }
};using IO::readll; using IO::readint; using IO::readc;
struct node{
  node *ls, *rs;
  int fix, size;
  LL value;
  LL lazy;
  LL maxv;
  node(LL x):size(1), fix(rand()){
    ls = rs = NULL;
    maxv = value = x;
    lazy = 0;
  }
  BETTER_CODE
  node *pushup_basic(){
    if(!this)return NULL;
    size = 1;
    if(ls)size += ls->size;
    if(rs)size += rs->size;
    return this;
  }
  BETTER_CODE
  node *pushup(){
    if(!this)return NULL;
    pushup_basic();
    maxv = value;
    if(ls)maxv = max(maxv, ls->maxv);
    if(rs)maxv = max(maxv, rs->maxv);
    return this;
  }
  BETTER_CODE
  void pushdown(){
    if(!this)return;
    if(lazy){
      ls->add(lazy);
      rs->add(lazy);
      lazy = 0;
    }
  }
  BETTER_CODE
  void add(LL v){
    if(!this)return;
    lazy += v;
    maxv += v;
    value += v;
  }
};
BETTER_CODE
node *merge(node *x, node *y){
  if(!x)return y->pushup_basic();  //和size有关的信息一定要这里重新维护
  if(!y)return x->pushup_basic();
  if(x->fix < y->fix){
    x->pushdown();
    x->rs = merge(x->rs, y);
    return x->pushup();
  }else{
    y->pushdown();
    y->ls = merge(x, y->ls);
    return y->pushup();
  }
}
typedef pair<node*, node*>droot;
BETTER_CODE
droot split(node *x, int k){
  droot r(NULL, NULL);
  if(!x)return r;
  x->pushdown();
  int s = x->ls?x->ls->size:0;
  if(s >= k){
    r = split(x->ls, k);
    x->ls = r.second;
    r.second = x->pushup();
  }else{
    r = split(x->rs, k-s-1);
    x->rs = r.first;
    r.first = x->pushup();
  }
  return r;
}
LL tmp[100001];
BETTER_CODE
node* build(LL *a, int n){
  node *x = new node(a[0]);
  for(int i = 1; i < n; i++)x = merge(x, new node(a[i]));
  return x;
}
void dfs(node *u){
  if(!u)return;
  u->pushdown();
  dfs(u->ls);
  printf("%lld\n", u->value);
  dfs(u->rs);
}
BETTER_CODE
int main(){
  freopen("equake.in", "r", stdin);
  freopen("equake.out", "w", stdout);
  srand(time(NULL));
  int n, q; n = readint(); q = readint();
  for(int i = 0; i < n; i++)tmp[i] = readll();
  node *root = build(tmp, n);
  while(q--){
    char c; while(!isalpha(c = readc()));
    switch(c){
      case 'I':{
        int ps = readint();
        int nw = readint();
        if(nw > 0){
          for(int i = 0; i < nw; i++)tmp[i] = readll();
          droot dpart = split(root, ps);
          root = merge(dpart.first, merge(build(tmp, nw), dpart.second));
        }
        break;
      }
      case 'R':{
        int l = readint();
        int r = readint();
        LL v = readll();
        droot p1 = split(root, l-1);
        droot p2 = split(p1.second, r-l+1);
        p2.first->add(v);
        root = merge(p1.first, merge(p2.first, p2.second));
        break;
      }
      case 'Q':{
        int l = readint();
        int r = readint();
        droot p1 = split(root, l-1);
        droot p2 = split(p1.second, r-l+1);
        printf("%lld\n", p2.first->maxv);
        root = merge(p1.first, merge(p2.first, p2.second));
        break;
      }
      case 'M':{
        int l = readint();
        int r = readint();
        droot p1 = split(root, l-1);
        droot p2 = split(p1.second, r-l+1);
        root = merge(p1.first, p2.second);
        break;
      }
    }
  }
  return 0;
}