杭电多校第二场 hdu 6315 Naive Operations 线段树变形
2024-08-29 08:13:19
Naive Operations
Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 502768/502768 K (Java/Others)
Total Submission(s): 2114 Accepted Submission(s): 915
Problem Description
In a galaxy far, far away, there are two integer sequence a and b of length n.
b is a static permutation of 1 to n. Initially a is filled with zeroes.
There are two kind of operations:
1. add l r: add one for al,al+1...ar
2. query l r: query ∑ri=l⌊ai/bi⌋
b is a static permutation of 1 to n. Initially a is filled with zeroes.
There are two kind of operations:
1. add l r: add one for al,al+1...ar
2. query l r: query ∑ri=l⌊ai/bi⌋
Input
There are multiple test cases, please read till the end of input file.
For each test case, in the first line, two integers n,q, representing the length of a,b and the number of queries.
In the second line, n integers separated by spaces, representing permutation b.
In the following q lines, each line is either in the form 'add l r' or 'query l r', representing an operation.
1≤n,q≤100000, 1≤l≤r≤n, there're no more than 5 test cases.
For each test case, in the first line, two integers n,q, representing the length of a,b and the number of queries.
In the second line, n integers separated by spaces, representing permutation b.
In the following q lines, each line is either in the form 'add l r' or 'query l r', representing an operation.
1≤n,q≤100000, 1≤l≤r≤n, there're no more than 5 test cases.
Output
Output the answer for each 'query', each one line.
Sample Input
5 12
1 5 2 4 3
add 1 4
query 1 4
add 2 5
query 2 5
add 3 5
query 1 5
add 2 4
query 1 4
add 2 5
query 2 5
add 2 2
query 1 5
1 5 2 4 3
add 1 4
query 1 4
add 2 5
query 2 5
add 3 5
query 1 5
add 2 4
query 1 4
add 2 5
query 2 5
add 2 2
query 1 5
Sample Output
1
1
2
4
4
6
1
2
4
4
6
Source
Recommend
题意：有个初始值为0的数组a，和一个数组b，每次可以对a数组所有数进行一次加一的操作，问每次查询时 a(l)/b(l) + a(l+1)/b(l+1) + ... + a(r)/b(r) 的和
分析：考虑我们要求的是[a1/b1] + [a2/b2] + ... + [an/bn]的和，看单独的项a1/b1，因为a1是从零开始的，所以只有当我们加的次数等于b1时（每次只加一），整体的和才会加一
a1每次加一一直加到b1相当于b1每次减一一直减到0（当bi的值减到一再重新赋值为bi这样可以一直进行加减操作），因为bi最开始的值是大于0的，所以我只需要用一个线段树来维护每次的最小值和区间和就行
#include <map>
#include <set>
#include <stack>
#include <cmath>
#include <queue>
#include <cstdio>
#include <vector>
#include <string>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <algorithm>
#define ls (r<<1)
#define rs (r<<1|1)
#define debug(a) cout << #a << " " << a << endl
using namespace std;
typedef long long ll;
const ll maxn = 1e5 + 1000;
const ll mod = 1e9 + 7;
struct node {
ll fg;
ll s; //一段区间总和
ll mv; //记录最小值
}root[4*maxn];
ll b[maxn], n, m, le, ri;
char s[10];
void update( ll r ) {
root[r].mv = min( root[ls].mv, root[rs].mv );
root[r].s = root[ls].s + root[rs].s;
}
void setf( ll r, ll f ) {
root[r].fg += f;
root[r].mv += f;
}
void build( ll r, ll le, ll ri ) {
root[r].fg = 0;
if( le == ri ) {
root[r].mv = b[le]-1;
root[r].s = 0;
} else {
ll mid = ( le + ri ) >> 1;
build( ls, le, mid );
build( rs, mid+1, ri );
update(r);
}
}
void push( ll r ) {
if( root[r].fg ) { //fg为-1进行操作，将左右子树最小值置为-1，同时将左右子树fg标记为-1
setf( ls, root[r].fg );
setf( rs, root[r].fg );
root[r].fg = 0;
}
}
ll query( ll r, ll le, ll ri, ll tl, ll tr ) {
if( tl == le && tr == ri ) {
return root[r].s;
} else {
push(r);
ll mid = ( le + ri ) >> 1;
if( tr <= mid ) {
return query( ls, le, mid, tl, tr );
} else if( tl > mid ) {
return query( rs, mid+1, ri, tl, tr );
} else {
return query( ls, le, mid, tl, mid ) + query( rs, mid+1, ri, mid+1, tr );
}
}
}
void modify( ll r, ll le, ll ri, ll tl, ll tr ) {
if( tl > tr ) {
return;
}
if( tl == le && tr == ri ) {
if( root[r].mv > 0 ) {
root[r].mv --, root[r].fg --;
} else {
if( tl == tr ) {
root[r].mv = b[le]-1;
root[r].s ++;
} else {
push(r);
ll mid = ( le + ri ) >> 1;
if( root[ls].mv == 0 ) {
modify( ls, le, mid, tl, mid );
} else {
setf( ls, -1 );
}
if( root[rs].mv == 0 ) {
modify( rs, mid+1, ri, mid+1, tr );
} else {
setf( rs, -1 );
}
update(r);
}
}
} else {
push(r);
ll mid = ( le + ri ) >> 1;
if( tr <= mid ) {
modify( ls, le, mid, tl, tr );
} else if( tl > mid ) {
modify( rs, mid+1, ri, tl, tr );
} else {
modify( ls, le, mid, tl, mid ), modify( rs, mid+1, ri, mid+1, tr );
}
update(r);
}
}
int main() {
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
while( scanf("%lld%lld",&n,&m) != EOF ) {
for( ll i = 1; i <= n; i ++ ) {
scanf("%lld",&b[i]);
}
build(1,1,n);
for( ll i = 1; i <= m; i ++ ) {
scanf("%s%lld%lld",s,&le,&ri);
if( s[0] == 'a' ) {
modify( 1, 1, n, le, ri );
} else {
printf("%lld\n",query(1,1,n,le,ri));
}
}
}
return 0;
}
最新文章
- UIAlertController 部分用法及属性
- C# 6.0 新特性
- 基于MVC4+EasyUI的Web开发框架形成之旅--基类控制器CRUD的操作
- knockout.js $index 做列表索引小技巧
- 最小生成树之Prime法
- mvc_ajax_for form
- 动态加载JS文件，并根据JS文件的加载状态来执行自己的回调函数
- Windows下PHP(Thread Safe与Non Thread Safe)版本说明
- Linux基础命令讲解（二）
- 严重：one or more listeners failed. Full details will be found in the appropriate container log file
- Postman的Tests标签测试
- Wannafly summer camp Day6 - D 区间权值
- ubuntu16.04 无法连接wifi和校园宽带问题的解决办法
- 3-D models provided some resources
- Symbol -- JavaScript 语言的第七种数据类型
- Webbrowser指定IE内核版本(更改注册表)
- grpc 实现微服务生态笔记
- Android Looper详解
- mongoengine在python中的使用
- 求最长公共子串 Ｌongest Common Subsequence