[Ynoi Easy Round 2021] TEST_152

Luogu

IDLGP8512

Time2500ms

Memory512MB

DifficultyP6

2021颜色段均摊（珂朵莉树 ODT）O2优化扫描线Ynoi

转转有一个长度为 $n$ 的操作序列 $(l_i,r_i,v_i)$。现在有 $q$ 个询问 $(L,R)$。对于每次询问，你初始有一个长度为 $m$ 的序列 $c$，初值全是 $0$。现在我们依次执行操作序列的第 $L,L+1,L+2,\cdots,R$ 项所对应的操作。每个操作是将序列 $c$ 的第 $l_i$ 项至第 $r_i$ 项赋值为 $v_i$。询问所有操作结束后整个序列 $c$ 中所有数的和。询问之间互相独立。 ## Input 第一行三个正整数 $n,m,q$。第 $2$ 行至第 $n+1$ 行，每行 $3$ 个正整数，第 $i+1$ 行表示 $l_i,r_i,v_i$。后面 $q$ 行，每行两个正整数，表示一次询问 $L,R$。 ## Output $q$ 行，每行一个正整数，表示询问的答案。 [samples] ## Note Idea：Ynoi，Solution：Ynoi，Code：Ynoi，Data：Ynoi 对于 $100\%$ 的数据，满足： $ 1 \le n,m,q \le 5 \times 10^5$ $ 1 \le l_i \le r_i \le m$ $0 \le v_i \le 2 \times 10^9$ $1 \le L \le R \le n$。

Samples

Input #1

Output #1

8
14
4

Input #2

Output #2

API Response (JSON)

{
  "problem": {
    "name": "[Ynoi Easy Round 2021] TEST_152",
    "description": {
      "content": "转转有一个长度为 $n$ 的操作序列 $(l_i,r_i,v_i)$。 现在有 $q$ 个询问 $(L,R)$。 对于每次询问，你初始有一个长度为 $m$ 的序列 $c$，初值全是 $0$。 现在我们依次执行操作序列的第 $L,L+1,L+2,\\cdots,R$ 项所对应的操作。 每个操作是将序列 $c$ 的第 $l_i$ 项至第 $r_i$ 项赋值为 $v_i$。 询问所有操作结束后整",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 2500,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P6"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP8512"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "转转有一个长度为 $n$ 的操作序列 $(l_i,r_i,v_i)$。\n\n现在有 $q$ 个询问 $(L,R)$。\n\n对于每次询问，你初始有一个长度为 $m$ 的序列 $c$，初值全是 $0$。\n\n现在我们依次执行操作序列的第 $L,L+1,L+2,\\cdots,R$ 项所对应的操作。\n\n每个操作是将序列 $c$ 的第 $l_i$ 项至第 $r_i$ 项赋值为 $v_i$。\n\n询问所有操作结束后整...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments