每周解题报告 (3rd, 8/14~8/20)

这周主要是尝试了一些新的东西( 做了一些之前一直想看但是一直没看懂和没做的题目。依旧是做 HDU 的题。虽然写得不是很熟练,不过慢慢来应该也是可以的。 另外下周由于要阶段考试这样子,可能就没有时间做题目了。

Stop
Modulation
Lyric offset(Current:0s)
+ 0.5s- 0.5s
Playing rate(x 1)+-
Loop:Disabled
Fullscreen mode
Developer mode
MUSE Player ver.5.7.5

やくそく三森すずこ / 花澤香菜

  • さよならじゃない今未来が始まるんだ这并不是永别 未来从现在才开始
  • 淡い蕾は花開いて祝福を歌う含苞待放的花蕾盛开 颂唱祝福之歌
  • 秘密の場所に埋めたのは在秘密场所里埋藏的是
  • 密かな夢と宝の地図潜藏于心的梦想与藏宝图
  • 時間巡りを閉じ込めた将反复的时间紧闭门中
  • 小さなガラスの欠片だった化成了小小的玻璃碎片
  • あの時 君は君は勇気を得た那时候 是你让我获得了勇气
  • 友を信じ抜く勇気を得た让我获得了坚信朋友的勇气
  • 永遠に消えない誇りになるだろう它会成为我永不消逝的骄傲吧
  • 最後の鐘が響き出す终结的钟声响起
  • たとえ涙が落ちてしまうとしても让我们发誓 即便再流下眼泪
  • 下を向いたりしないと誓おう也不再低下头
  • そっと重ねた思い出の数だけ只有那默默积累下的记忆
  • 光ゆらめいて背中を押した在虚渺的光芒中一直支持着我
  • 流れ続ける砂時計のような時よ时间仿佛不断流逝的沙漏
  • 翼広げてさあ飛び立とう地平線の果て张开双翼 向着地平线的尽头翱翔吧
  • あどけなかった横顔が你那天真烂漫的侧脸
  • 凛々しくなったはいつの日か不知在何时已变得如此冷酷严峻
  • 速まる日々に負けぬよう为了不输给忙碌的生活
  • 毎日夢中で追いかけてた每日都不顾一切地追赶
  • あの時君は君は希望を見た在那时 是你让我看见了希望
  • 暗闇に浮かぶ 希望を見た让我看见了在黑暗中浮现的希望
  • 行き先照らす明かりになるだろう它会成为我通向终点的照明灯吧
  • もう迷うことはないんだ我已经不会再次迷失自我了
  • いつか傷つくことがあるとしても即便在未来某刻会受伤
  • 友がくれた言葉を胸に朋友托付于我的咒语 也会在我心中
  • 傷を癒して進み続けるよ治愈着我的伤痕 让我向前迈进
  • きっとその先でまた会えるから一定会在前方再次相遇吧
  • あの時君は君は勇気を得た那时候 是你让我获得了勇气
  • 友を信じ抜く勇気を得た让我获得了坚信朋友的勇气
  • 永遠に消えない誇りになるだろう它会成为我永不消逝的骄傲吧
  • 最後の鐘が響き出す终结的钟声响起
  • たとえ 涙が落ちてしまうとしても让我们发誓 即便再流下眼泪
  • 下を向いたりしないと誓おう也不再低下头
  • そっと重ねた思い出の数だけ只有那默默积累下的记忆
  • 光ゆらめいて背中を押した在虚渺的光芒中一直支持着我
  • あのね ありがとう またあの場所で我想对你说 谢谢你 让我们再次在那个地方相遇吧
  • 歌词作者:lyricshare
  • 1やくそく三森すずこ / 花澤香菜

    8200, HDU5489, Removed Interval

    题意 & 扯淡

    题意就是已知一个数列,从中删除连续的 n 个数,然后要使得删除完之后它的最长上升子序列最大。n <= 1e5.

    这题好像有很多的解法,有用传统 LIS 做的,还有用 LIS + BIT 或者 LIS + Segment Tree 做的……后面两种做法没能理解(说实话,第一种做法也没怎么能理解),所以我还是硬着头皮看了一下直接做的。

    所谓题解

    因为要从数列中删除一些数之后求 LIS,然后就是我们枚举删除的数的终点,然后对终点右边的第一个数为起点求一次 LIS 然后再从最左边到删除的起点求一次 最大的数不超过终点右边第一个数 的 LIS 从右往左的这个 LIS 必须在枚举起点之前预处理求出,所以: 从右往左求 LIS 可以用负数的方法来做,然后倒着求回来,一直从 n 求到 l 为止。

    代码

    #include <bits/stdc++.h> 
    using namespace std;
    
    const int MAXN = 1e5 + 10;
    const int INF = 1e9 + 7;
    
    int kases, tmp;
    int n, l;
    int a[MAXN], b[MAXN], dp[MAXN], LIS[MAXN];
    
    int main()
    {
      scanf("%d", &kases);
      
      while (kases--)
      {
        tmp++;
        scanf("%d%d", &n, &l);
        
        fill(dp, dp + MAXN, INF);
        
        for (int i = 0; i < n; i++)
        {
          scanf("%d", &a[i]);
          b[i] = -a[i];
        }
        
        // reverse LIS
        int pos = 0;
        fill(LIS, LIS + MAXN, INF);
        
        for (int i = l; i >= l; i--)
        {
          pos = lower_bound(LIS, LIS + n, b[i]) - LIS;
          LIS[pos] = b[i];
          dp[i] = pos + 1;
        }
        
        int ans = 0, maxlen = 0;
        fill(LIS, LIS + MAXN, INF);
        for (int i = l; i < n; i++)
        {
          pos = lower_bound(LIS, LIS + n, a[i]) - LIS;      // from left to right
          ans = max(ans, pos + 1 + dp[i] - 1);        // >=
    
          pos = lower_bound(LIS, LIS + n, a[i - l]) - LIS;    // update left LIS
          LIS[pos] = a[i-l];
          maxlen = max(maxlen, pos + 1);
        }
        ans = max(ans, maxlen);
        printf("Case #%d: %d\n", tmp, ans);
      }
      
      return 0;
    }
    

    9200, HDU1074, Doing Homework

    扯淡

    DP,而且不是一般的 DP……是状压 DP 的说。这种 DP 也不是很好理解也很难想……主要还是要写题积累经验。算是我的第一道状压吧 QAQ,之前一直以为状压 DP 涉及各种二进制和位操作挺可怕的……看理论什么的也一直看不太懂。

    题解

    嘛……这是我有生以来写过的第一道状态压缩 DP 的题……第一眼看到 N <= 15 就有种不好的预感 2333……

    状态压缩嘛,就是把 DP 中用到的状态用二进制来表示,然后就这道题目理解了一下状态压缩 DP 的基本的写法,下面是我稍微总结的一下状态压缩 DP 的框架:

    const MAXN = 最大的状态点数目
    const MAXS = 1 << MAXN			// 最多的状态数,表示 2^MAXN 个
    var dp[MAXS]				// DP 数组
    
    read n
    
    for (i = 1...(1 << n))			// 枚举每个用二进制表示的状态
        for (j = 0....n)			// 枚举每一个点
            var cur = 1 << j		// 当前点用二进制表示后的整数
    	if (i & cur)			// 判断当前状态是否合法,即当前枚举的状态 (i) 必须包含当前枚举的点 (cur)
                var last = i - cur		// 这一步是可选的,如果你要获得当前状态的上一个状态
    					// 那么可以用当前枚举的状态减去当前枚举的点的二进制状态
    
                dp equation			// 那么现在就可以开始你的 DP 方程了
    
    print dp[(1 << n) - 1]			// 最终答案就是 dp[(1 << n) - 1] 了
    

    然后说回到这一题上吧。题意就是某人要做好多的作业,每个作业有一个上交期限 deadline 和需要花费的时间 cost。如果每超过一天上交就扣一分,然后让你求出扣分最少的方案并输出字典序最小的方案。

    由于最多只有 15 个状态点,那么用二进制表示这 15 个状态点的话,十进制的数不会超过 2^15 = 32768,所以我们想到用状压 DP 来解。那么,设整数 i 为用二进制表示了当前状态然后转换后的十进制数,然后我们就可以开一个数组 dp[1…MAXS] 来表示对于每个状态扣的分最少是多少,这里我们用二进制来表示状态,即用 0 来表示未完成这个作业,1 表示已完成这个作业。然后我们就可以从低位向高位填充来表示是否坐过这个作业了。

    例如说有 5 门作业,你做了 第一门、第二门和第五门,那么用二进制表示就是 10011,然后转成十进制数就是 19.

    我们用 i 枚举当前状态,然后再枚举一维 j 表示当前枚举的状态点(每一科的作业),当 i 状态包含了当前状态点的时候我们就可以根据我们的 DP 方程对 dp 数组进行更新。具体地,我们可以判断 i & (1 << j) 是否等于 1 的结果来看,如果等于 1 的话那么 i 状态就完成了第 j 门功课。

    dp 方程如下(不要忘记转移的同时更新时间):

    dp[i].score = dp[prev].score + max(dp[prev].time + lesson[j].cost - lesson[j].deadline, 0)
    

    我们记 curscore = 在完成第 j 门作业前的上一个状态(可以用 i - (1 << j) 来求得上一个状态)已经花费掉的时间 + 做当前作业需要花费的时间 - 当前作业的 deadline,那么 curscore 有两种情况:1. 当 curscore > 0 的时候,就是当前决策会被扣掉的分数;2. 当 curscore <= 0 的时候,表明当前决策还不会被扣分,但是提早上交作业也不会加分,所以我们要把它设为 0.

    然后呢看题目要求除了输出最小代价之外还要输出方案,那么我们可以用一个结构体来表示当个状态,除了记录代价 score 和所用时间 times 外还需要记录上一个状态 prev 和当前的科目 subject. 利用最终答案是 dp[(1 << n) - 1] 这个性质,我们就可以通过 prev 回溯回去输出方案了,具体的做法就是从最终状态往前搜寻,并把它们加入一个栈中。然后你知道怎么做了。

    还有一个要注意的地方就是边界处理,不然会无限 WA。

    代码

    #include <bits/stdc++.h> 
    
    using namespace std;
    
    const int MAXN = 15;
    const int MAXS = 1 << MAXN;
    const int INF = 1e9 + 7;
    
    struct Lesson {
      int deadline;
      int need;
      char name[105];
    };
    
    struct State {
      int day;
      int doing;
      int score;
      int previous;
    };
    
    Lesson les[MAXN];
    State dp[MAXS];
    
    int cases;
    int n, l;
    
    int main()
    {
      scanf("%d", &cases);
      while (cases--)
      {
        memset(dp, 0, sizeof(dp));
        
        scanf("%d", &n);
        
        for (int i = 0; i < n; i++)
        {
          cin >> les[i].name >> les[i].deadline >> les[i].need;
        }
        
        int terminal = 1 << n;
        
        // state-compressing
        for (int i = 1; i < terminal; i++)
        {
          dp[i].score = INF;
          for (int j = n - 1; j >= 0; j--)
          {
            int current = 1 << j;
            if (i & current)
            {
              int prev = i - current;     // previous state
              int score = dp[prev].day + les[j].need - les[j].deadline;
              if (score < 0)
                score = 0;
                
              int newState = score + dp[prev].score;
              if (newState < dp[i].score)
              {
                dp[i].score = newState;
                dp[i].day = dp[prev].day + les[j].need;
                dp[i].previous = prev;
                dp[i].doing = j;
              }
            }
          } // for j = n-1 => 0
        } // for i = 1 => terminal
        
        printf("%d\n", dp[terminal - 1].score);
        
        // print solutions
        stack<int> solutions;
        int cur = terminal - 1;
        while (cur != 0)
        {
          solutions.push(dp[cur].doing);
          cur = dp[cur].previous;
        }
        
        while (!solutions.empty())
        {
          printf("%s\n", les[solutions.top()].name);
          solutions.pop();
        }
      }
      
      return 0;
    }
    

    10100, HDU3192, Hamburger Magi

    题意 & 扯淡

    第二道状压。具体的题意看题解吧,其实这些解题报告都是我把写完一题的时候 YY 出来的题解拼出来的,所以就不想浪费时间排版什么的了,看得懂找得到就行。

    题解

    感觉状态压缩的题目写的还是不太多,然后就没有那种感觉……不过经过上一题之后看到这道题就有些靠谱的思路了,虽然因为掉进了上一题的思维定式里然后 WA 了好几回 QAQ……

    这一题的话,题意大概就是要做汉堡包,然后每个汉堡包有自己的价值 v(下文用 val 表示) 和制作所需要的能量 e(用 cost 表示),总共可以消耗的能量为 E. 再然后就是有些种类的汉堡包可能有“依赖”,也即在做他们之前需要有些汉堡包已经做好了。每种汉堡包最多做一个,然后综合上述条件,求出满足题意的最大价值 maxVal. 1 <= n <= 15.

    老规律,看到 n <= 15 就想到状态压缩 DP。这道题和上一题有个比较不一样的地方在于,上一题是根据当前枚举到的状态作为已知,而当前状态的先前一个状态未知,所以是从后向前推的;这道题是把当前枚举到的状态作为已知,当前状态的下一个状态未知,然后要从前向后推。

    我们记 i 为当前汉堡种类的状态,用 j 表示下一个状态相较当前状态多做的汉堡种类,在 DP 之前我们先要判断条件是否合适。由于这题当中有一个“依赖”的概念,又有一个能量的限定,所以我们在判断 DP 状态是否合法的时候要注意一下。由于前一个“依赖”的限定是硬性的,也就是这个限制只能在我们 DP 下一个状态之前先判断当前状态能否推出下一个状态;但是对于“能量”这个限定就显得比较宽松,我们既可以边 DP 边剪枝,把所需能量大于总能量的解答直接剪掉;也可以暂时不剪掉,但是记录它们的花费(尽管有时候该花费已经超过了总能量),然后在 DP 完成之后循环一遍 dp 数组,这个时候就可以很方便地根据 dp[i].cost 来判断状态是否合法了,因为这个值已经固定下来不会改变了,所以我们可以在状态合法的前提下更新答案。网上的题解大致也分这两种写法,我觉得后面一种比较好理解也好写,所以我们用第二种做法。

    至于判断依赖是否满足的话,我们遍历 j 的每一个依赖 deps[j][x],如果 (i & (1 << j 的每一个依赖)),说明当前状态合法,可以由当前状态推向下一个状态;反之则不能从当前状态通过做第 j 个汉堡包达到下一个状态。

    DP 方程如下,设 items[j] 为第 j 种汉堡的信息,i 为在 n 个不同的状态点的二进制状态转换成的十进制数,那么:

    dp[i | (1 << j)].val = dp[i].val + items[j].val, dp[i | (1 << j)].cost = dp[i].cost + items[j].cost;
    

    这里的 (1 << j) 表示一个“只做当前枚举的第 j 个汉堡的二进制状态”,i 是当前状态,由于 (1 << j) 二进制下只有第 j 位是 1 其他都是 0(注意这里 j 的下标是从 0 开始的),所以 i 与 1 << j 按位或返回的结果就是下一个状态。

    做完 DP 之后循环一遍 dp 数组更新 ans 就可以了: ans = max(ans, dp[i].val), 其中 dp[i].cost <= E.

    代码

    #include <bits/stdc++.h>
    using namespace std;
    
    const int MAXN = 15;
    const int MAXS = 1 << 15;
    const int INF = 1e9 + 7;
    
    struct Hamburger {
      int val;
      int cost;
      int dep;
      int deps[15];
    };
    Hamburger items[MAXN];
    
    struct State {
      int val;
      int cost;
    };
    State dp[MAXS];
    
    int cases;
    int n, e;
    
    int main()
    {
      scanf("%d", &cases);
      
      while (cases--)
      {
        memset(items, 0, sizeof(items));
        memset(dp, -1, sizeof(dp));
        
        scanf("%d%d", &n, &e);
        for (int i = 0; i < n; i++)
        {
          scanf("%d", &items[i].val);
        }
        for (int i = 0; i < n; i++)
        {
          scanf("%d", &items[i].cost);
        }
        for (int i = 0; i < n; i++)
        {
          scanf("%d", &items[i].dep);
          if (items[i].dep > 0)
          {
            for (int j = 0; j < items[i].dep; j++)
            {
              scanf("%d", &items[i].deps[j]);
              items[i].deps[j]--;
            }
          }
        } // end read
        
        int end = 1 << n;
        int ans = 0;
    
        dp[0].cost = 0, dp[0].val = 0;
    
        for (int i = 0; i < end; i++)
        {
          if (dp[i].cost == -1)
            continue;
            
          for (int j = 0; j < n; j++)
          {
            int cur = 1 << j;
            if (!(i & cur))
            {
              int next = i | cur;
              
              bool flag = true;
              if (items[j].dep > 0)
              {
                for (int x = 0; x < items[j].dep; x++)
                {
                  int depState = 1 << items[j].deps[x];
                  if (!(i & depState)) {
                    flag = false;
                    break;
                  }
                } // for x = 0 -> items[j].dep
              } // if items[j].dep > 0
              
              if (flag)
              {
                dp[next].val = dp[i].val + items[j].val;
                dp[next].cost = dp[i].cost + items[j].cost;
              }
              
            } // if i & cur
          } // for j = 0 -> n
        } // for i = 1 -> end
    
        for (int i = 0; i < end; i++)
        {
          if (dp[i].cost <= e)
            ans = max(ans, dp[i].val);
        }
      
        printf("%d\n", ans);
    
      }
      
      return 0;
    }
    
    

    11200, HDU1520, Anniversary Party

    题意 & 扯淡

    树形 DP 入门题,是之前突然想学学树形 DP 的时候找到的。题意大概就是一个宴会上要邀请员工,每个员工都有一个开心指数,只有在宴会上见不到自己的直属上司的时候才会开心,然后要求出开心指数的最大值。

    题解

    这道题有个很坑的地方就是它一个样例有好多个子任务,但是它什!么!都!没!说! * 然后我交了 7 遍还是不知道为什么 WA 的……找了个 std 一看,卧槽要处理多组数据……

    设 dp[i][0] 为不邀请第 i 个人的最大值, dp[i][1] 为邀请第 i 个人的最大值。如果我们邀请了第 i 个人,那么我们就不能邀请第 i 个人的直接下属,但是他的直接下属的下属是可以邀请的……然后按照这个思路转移方程就出来了。

    首先要建树,然后这里我采用的是用图的保存方法,直接用了 vector[MAXN] 数组来存第 i 个人的直接下属。首先找到树根,也就是入度为 0 的(没有父亲或者说父亲是本身的)那个节点 Q,然后以此节点为起点做一遍 DFS,边 DFS 边状态转移,之后输出答案就好了。

    状态转移方程如下:

    dp[i][0] = max(dp[k1][0], dp[k1][1]) + ... + max(dp[kx][0], dp[kx][1])
    // 其中 k1 ... kx 是第 i 个员工的所有直属下属的下标
    
    dp[i][1] = dp[k1][0] + dp[k2][0] + ... + dp[kx][0]
    // 假如第 i 个员工要出席宴会,这种情况下他的直接下属都不能参加
    

    然后答案就是 ans = max(dp[Q][0], dp[Q][1]);.

    代码

    #include <bits/stdc++.h> 
    using namespace std;
    
    const int MAXN = 6010;
    int n;
    int rate[MAXN], p[MAXN];
    int dp[MAXN][2];
    vector<int> T[MAXN];
    
    void dfs(int s)
    {
      if (T[s].size() == 0)
      {
        dp[s][1] = rate[s];
        dp[s][0] = 0;
        return;
      }
      
      for (int i = 0; i < T[s].size(); i++)
      {
        int cur = T[s][i];
        dfs(cur);
        dp[s][0] += max(dp[cur][1], dp[cur][0]);
        dp[s][1] += dp[cur][0];
      }
      dp[s][1] += rate[s];
      return;
    }
    
    int main()
    {
      while (scanf("%d", &n) != EOF)
      {
        memset(rate, 0, sizeof(rate));
        memset(p, 0, sizeof(p));
        memset(dp, 0, sizeof(dp));
        
        for (int i = 0; i <= MAXN; i++)
        {
          T[i].clear();
        }
        
        for (int i = 1; i <= n; i++)
        {
          scanf("%d", &rate[i]);
        }
        
        int x, y;
        while (scanf("%d%d", &x, &y) != EOF && x != 0 && y != 0)
        {
          T[y].push_back(x);
          p[x] = y;
        }
        
        int s;
        for (int i = 1; i <= n; i++)
        {
          if (p[i] == 0)
          {
            s = i;
            break;
          }
        }
        
        dfs(s);
        int ans = max(dp[s][0], dp[s][1]);
        printf("%d\n", ans);    
      }
      return 0;
    }
    
    

    12200, HDU1166, 敌兵布阵

    题意自己看原题吧 Orz 反正是中文的,这题用 BIT 和单点修改的线段树都可以做,是个裸的板子题。记一下这道题的板子代码以防将来需要。

    BIT version

    因为只有单点修改,所以用树状数组完全可以胜任。

    #include <bits/stdc++.h>
    
    const int MAXN = 50005;
    int n;
    int c[MAXN];
    
    int lowbit(int x)
    {
      return x & (-x);
    }
    
    void add(int i, int value)
    {
      while (i <= n)
      {
        c[i] += value;
        i += lowbit(i);
      }
    }
    
    int sum(int x)
    {
      int res = 0;
      while (x > 0)
      {
        res += c[x];
        x -= lowbit(x);
      }
      return res;
    }
    
    int main()
    {
      int t;
      scanf("%d", &t);
      
      for (int i = t; i > 0; i--)
      {
        printf("Case %d:\n", t - i + 1);
        scanf("%d", &n);
        memset(c, 0, sizeof(c));
        
        for (int j = 1; j <= n; j++)
        {
          int x;
          scanf("%d", &x);
          add(j, x);
        }
        
        char str[10];
        int x, y;
        while (scanf("%s", str) != EOF && str[0] != 'E')
        {
          scanf("%d%d", &x, &y);
          
          if (str[0] == 'Q') {
            int res = sum(y) - sum(x-1);
            printf("%d\n", res);
          }
          
          if (str[0] == 'A') {
            add(x, y);
          }
          
          if (str[0] == 'S') {
            add(x, -y);
          }
        }
        
      }
      
      return 0;
    }
    
    

    Segment Tree version

    线段树的单点修改区间查询版也可以做这题,如下。写起来会比树状数组的版本麻烦一些。记得一个很重要的地方就是线段树的数组要开到 MAXN 的 4 倍。

    #include <bits/stdc++.h> 
    const int MAXN = 50010;
    
    int n;
    int kases, tmp;
    
    struct SegTree
    {
      int sum[MAXN << 2];
      
      void pushUp(int root) 
      {
        sum[root] = sum[root * 2] + sum[root * 2 + 1];
      }
      
      void build(int left, int right, int root)
      {
        if (left == right)
        {
          scanf("%d", &sum[root]);
          return;
        }
        int middle = (left + right) / 2;
        build(left, middle, root * 2);
        build(middle + 1, right, root * 2 + 1); 
        
        pushUp(root);
      }
      
      void update(int left, int right, int root, int pos, int addVal)
      {
        if (left == right)
        {
          sum[root] += addVal;
          return;
        }
        int middle = (left + right) / 2;
        
        if (pos <= middle)
        {
          update(left, middle, root * 2, pos, addVal);
        }
        else
        {
          update(middle + 1, right, root * 2 + 1, pos, addVal);
        }
        
        pushUp(root);
      }
      
      int query(int from, int to, int left, int right, int root)
      {
        if (from <= left && right <= to)
        {
          return sum[root];
        }
        
        int middle = (left + right) / 2;
        
        int res = 0;
        if (to <= middle)
        {
          res += query(from, to, left, middle, root * 2);
        }
        else if (from > middle)
        {
          res += query(from, to, middle + 1, right, root * 2 + 1);
        }
        else
        {
          res += query(from, to, left, middle, root * 2) + query(from, to, middle + 1, right, root * 2 + 1);
        }
        
        return res;
      }
      
      void init()
      {
        for (int i = 0; i < MAXN; i++)
        {
          sum[i] = 0;
        }
      }
    };
    
    SegTree tree;
    
    int main()
    {
      scanf("%d", &kases);
      
      while (kases--) 
      {
        tmp++;
        printf("Case %d:\n", tmp);
        
        scanf("%d", &n);
        
        tree.init();
        tree.build(1, n, 1);
        
        char commands[20];
        while (scanf("%s", commands) != EOF && commands[0] != 'E')
        {
          if (commands[0] == 'Q')
          {
            int x, y;
            scanf("%d%d", &x, &y);
            
            int res = tree.query(x, y, 1, n, 1);
            printf("%d\n", res);
          }
          
          if (commands[0] == 'A')
          {
            int x, y;
            scanf("%d%d", &x, &y);
            tree.update(1, n, 1, x, y);
          }
          
          if (commands[0] == 'S')
          {
            int x, y;
            scanf("%d%d", &x, &y);
            tree.update(1, n, 1, x, -y);
          }
        }
      }
      
      return 0;
    }
    
    
    Powered By Valine
    v1.5.2