首页 > 代码库 > 卿学姐与公主

卿学姐与公主

2024-11-02 17:24:39   205人阅读

卿学姐与公主

Time Limit: 2000/1000MS (Java/Others)     Memory Limit: 65535/65535KB (Java/Others)

某日，百无聊赖的卿学姐打开了某11区的某魔幻游戏

在这个魔幻的游戏里，生活着一个美丽的公主，但现在公主被关押在了魔王的城堡中。

英勇的卿学姐拔出利刃冲向了拯救公主的道路。

走过了荒野，翻越了高山，跨过了大洋，卿学姐来到了魔王的第一道城关。

在这个城关面前的是魔王的精锐部队，这些士兵成一字排开。

卿学姐的武器每次只能攻击一个士兵，并造成一定伤害，卿学姐想知道某时刻从L到R这个区间内，从开始到现在累计受伤最严重的士兵受到的伤害。

最开始每个士兵的受到的伤害都是0

Input

第一行两个整数N,Q表示总共有N个士兵编号从1到N，和Q个操作。

接下来Q行，每行三个整数，首先输入一个t，如果t是1，那么输入p,x，表示卿学姐攻击了p这个位置的士兵，并造成了x的伤害。如果t是2，那么输入L,R，表示卿学姐想知道现在[L,R]闭区间内，受伤最严重的士兵受到的伤害。

1≤N≤100000

1≤Q≤100000

1≤p≤N

1≤x≤100000

1≤L≤R≤N

Output

对于每个询问，回答相应的值

Sample input

5 42 1 21 2 41 3 52 3 3

Sample Output
05

Hint

注意可能会爆int哦

 

 

//线段树，树状数组求最大值，模板题

树状数组

技术分享
 1 #include <bits/stdc++.h> 2 using namespace std; 3 #define LL long long 4 #define MX 100005 5  6 int n; 7 LL A[MX]; 8 LL C[MX]; 9 int lowbit(int x){10     return x&(-x);11 }12 13 void update(int p)14 {15     while (p<=n)16     {17         C[p]=A[p];18         for (int i=1;i<lowbit(p);i<<=1)19             C[p]=max(C[p],C[p-i]);20         p+=lowbit(p);21     }22 }23 24 LL query(int x,int y)25 {26     LL ret = 0;27     while (y>=x)28     {29         ret = max(ret,A[y]);30         y--;31         while (y-lowbit(y)>=x)32         {33             ret = max (ret,C[y]);34             y-=lowbit(y);35         }36     }37     return ret;38 }39 40 int main()41 {42     while (scanf("%d",&n)!=EOF)43     {44         int q;45         scanf("%d",&q);46         memset(A,0,sizeof(A));47         memset(C,0,sizeof(C));48         while (q--)49         {50             int op;51             scanf("%d",&op);52             if (op==1)53             {54                 int p,x;55                 scanf("%d%d",&p,&x);56                 A[p]+=x;57                 update(p);58             }59             else if (op==2)60             {61                 int x,y;62                 scanf("%d%d",&x,&y);63                 printf("%lld\n",query(x,y));64             }65         }66     }67     return 0;68 }
View Code

线段树

技术分享
 1 #include <bits/stdc++.h> 2 using namespace std; 3 #define LL long long 4 #define MX 100005 5 struct Node 6 { 7     int l,r; 8     LL m; 9 }tree[MX*4];10 int n;11 12 void Init(int l,int r,int k)13 {14     tree[k].l=l,15     tree[k].r=r;16     tree[k].m=0;17     if (l==r) return ;18 19     int mid = (l+r)>>1;20     Init(l,mid,2*k);21     Init(mid+1,r,2*k+1);22 }23 24 LL update(int l,int r,int k,int w)25 {26     if (l==tree[k].l&&tree[k].r==r)27     {28         tree[k].m+=w;29         return tree[k].m;30     }31     int mid = (tree[k].l+tree[k].r)>>1;32     if (r<=mid) update(l,r,2*k,w);33     else if (l>=mid+1) update(l,r,2*k+1,w);34     else update(l,mid,2*k,w),update(mid+1,r,2*k+1,w);35     tree[k].m= max(tree[2*k].m,tree[2*k+1].m);36     return tree[k].m;37 }38 39 LL query(int l,int r,int k)40 {41     if (tree[k].l==l&&tree[k].r==r)42     {43         return tree[k].m;44     }45     int mid = (tree[k].l+tree[k].r)>>1;46     if (r<=mid) return query(l,r,2*k);47     else if (l>=mid+1) return query(l,r,2*k+1);48     return max(query(l,mid,2*k),query(mid+1,r,2*k+1));49 }50 51 int main()52 {53     int n;54     while (scanf("%d",&n)!=EOF)55     {56         Init(1,n,1);57         int q;58         cin>>q;59         while (q--)60         {61             int op;62             scanf("%d",&op);63             if(op==1)64             {65                 int q,x;66                 scanf("%d%d",&q,&x);67                 update(q,q,1,x);68             }69             else if (op==2)70             {71                 int x,y;72                 scanf("%d%d",&x,&y);73                 printf("%lld\n",query(x,y,1));74             }75         }76     }77     return 0;78 }
View Code

 

卿学姐与公主


联系
我们