考试时候怎么就是没想到线段树分治呢？

题目描述

《贪玩蓝月》是目前最火爆的网页游戏。在游戏中每个角色都有若干装备，每件装备有一个特征值 $w$ 和一个战斗力 $v$ 。在每种特定的情况下，你都要选出特征值的和对 $\rm MOD$ 取模后在一段范围内的装备，而角色死亡时自己的装备会爆掉。每个角色的物品槽可以看成一个双端队列，得到的装备会被放在两端，自己的装备爆掉也会在两端被爆。

现在我们有若干种事件和询问，如下所示：

• IF w v：在前端加入一件特征值为 $w$ 战斗力为 $v$ 的装备
• IG w v：在后端加入一件特征值为 $w$ 战斗力为 $v$ 的装备
• DF：删除最前端的装备
• DG：删除最后端的装备
• QU l r：在当前的装备中选取若干装备，他们的和对 $\rm MOD$ 取模后在 $[l, r]$ 中，使得这些装备的战斗力之和最大

为了锻炼你的水平，请尽量使用在线做法。

---

题目分析

做法一：线段树分治

考虑一下w,v强制在线的做法。

注意到这个在线是个“半在线”：因为虽然w,v是被加密过的，但是操作种类是可见的。那么就可以预先处理处每一个物品的存在时间区间，因此这样对操作进行线段树分治就是个离线问题了。

1 #include
     
       2 typedef long long ll; 3 const int maxn = 50035; 4  5 int m,p,tag; 6 ll ans[maxn]; 7 struct QRs 8 { 9     char opt[5];10     int l,r;11 }qr[maxn];12 struct Opt13 {14     int s,t,w,v;15     Opt(int a=0, int b=0, int c=0, int d=0):s(a),t(b),w(c),v(d) {}16 }rec[maxn];17 struct node18 {19     ll f[503],g[503];20     void init()21     {22         memset(f, -0x3f3f3f3f, sizeof f), f[0] = 0;23     }24     void update(int w, int v)25     {26         for (int i=0; i
      
        vec;38 std::deque
       
         deq;39 vec opt;40 41 int read()42 {43     char ch = getchar();44     int num = 0, fl = 1;45     for (; !isdigit(ch); ch=getchar())46         if (ch=='-') fl = -1;47     for (; isdigit(ch); ch=getchar())48         num = (num<<1)+(num<<3)+ch-48;49     return num*fl;50 }51 void solve(int l, int r, vec opt, node sta)52 {53     vec L,R;54     int mid = (l+r)>>1;55     for (int i=0, mx=opt.size(); i
        
         <= t) sta.update(opt[i].w, opt[i].v);59         else{60             if (s <= mid) L.push_back(opt[i]);61             if (t > mid) R.push_back(opt[i]);62         }63     }64     if (l==r){65         if (qr[l].opt[0]=='Q') ans[l] = sta.query(qr[l].l, qr[l].r);66     }else solve(l, mid, L, sta), solve(mid+1, r, R, sta);67 }68 int main()69 {70     scanf("%*d"), m = read(), p = read();71     for (int i=1, tmp; i<=m; i++)72     {73         scanf("%s",qr[i].opt);74         if (qr[i].opt[0]=='I'){75             qr[i].l = read()%p, qr[i].r = read(), ++tag;76             if (qr[i].opt[1]=='F') deq.push_front(tag);77             else deq.push_back(tag);78             opt.push_back(Opt(i, m, qr[i].l, qr[i].r));79         }80         if (qr[i].opt[0]=='Q')81             qr[i].l = read(), qr[i].r = read();82         if (qr[i].opt[0]=='D'){83             if (qr[i].opt[1]=='F')84                 tmp = deq.front(), deq.pop_front();85             else tmp = deq.back(), deq.pop_back();86             opt[tmp-1].t = i-1;87         }88     }89     sta.init();90     solve(1, m, opt, sta);91     for (int i=1; i<=m; i++)92         if (qr[i].opt[0]=='Q') printf("%lld\n",ans[i]);93     return 0;94 }
        
       
      
     

做法二：思维题  栈  启发式

可能要先咕着