TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P1909
  • 题目
  • P1909【线段树】战场控制系统
    限制 : 时间限制 : 20000 MS   空间限制 : 65536 KB
    问题描述

    2050年,人类与外星人之间的战争已趋于白热化。就在这时,人类发明出
    一种超级武器,这种武器能够同时对相邻的多个目标进行攻击。凡是防御力小于或
    等于这种武器攻击力的外星人遭到它的攻击,就会被消灭。然而,拥有超级武器是
    远远不够的,人们还需要一个战地统计系统时刻反馈外星人部队的信息。这个艰巨
    的任务落在你的身上。请你尽快设计出这样一套系统。

    这套系统需要具备能够处理如下2类信息的能力:

    1.外星人向[x1,x2]内的每个位置增援一支防御力为v的部队。
    2.人类使用超级武器对[x1,x2]内的所有位置进行一次攻击力为v的打击。系统需
    要返回在这次攻击中被消灭的外星人个数。

    注:防御力为i的外星人部队由i个外星人组成,其中第j个外星人的防御力为j。

    输入格式

    第一行读入n,m。其中n表示有n个位置,m表示有m条信息。
    以下有m行,每行有4个整数k,x1,x2,v用来描述一条信息 。k表示这条信息属
    于第k类。x1,x2,v为相应信息的参数。k=1 or 2。
    注:你可以认为最初的所有位置都没有外星人存在。
    规模:0<n<=1000;0<x1<=x2<=n;0<v<=1000;0<m<=2000

    输出格式

    按顺序输出需要返回的信息。

    样例输入

    3 5
    1 1 3 4
    2 1 2 3
    1 1 2 2
    1 2 3 1
    2 2 3 5

    样例输出

    6
    9