2017 CCPC 杭州 HDU6273J 区间修改(线段树&差分数组)
2024-09-07 21:16:34
http://acm.hdu.edu.cn/downloads/CCPC2018-Hangzhou-ProblemSet.pdf
解析 线段树区间延迟更新 或 差分数组 两个数 统计2和3的最少的个数 乘一下
差分数组https://blog.csdn.net/yao166164474/article/details/52675613
AC代码
#include<iostream>
#include<cstring>
#include<cstdio>
#include<map>
#include<algorithm>
#include<cmath>
#define ll long long
#define PI acos(-1.0)
const int inf = 0x3f3f3f3f,mod=;
using namespace std;
struct node
{
ll l,r;
ll add;
ll sum;
} tree1[],tree2[];
void pushup(ll root,node tree[])
{
tree[root].sum=min(tree[root<<].sum,tree[root<<|].sum);
}
void buildtree(ll root,ll left,ll right,node tree[])
{
tree[root].l=left;
tree[root].r=right;
tree[root].add=;//wa点 所有的延迟标记都要初始化
if(left==right)//不能放到下面的if中
{
tree[root].sum=;
return ;
}
ll mid=(left+right)>>;
buildtree(root<<,left,mid,tree);
buildtree(root<<|,mid+,right,tree);
pushup(root,tree);
}
void pushdown(ll root,node tree[])
{
if(tree[root].add==) return ;
tree[root<<].add+=tree[root].add;//wa点 这里是增加而不是赋值
tree[root<<|].add+=tree[root].add;
tree[root<<].sum+=tree[root].add;
tree[root<<|].sum+=tree[root].add;
tree[root].add=;
}
void updata(ll root,ll left,ll right,ll c,node tree[])
{
if(tree[root].l==left&&tree[root].r==right)
{
tree[root].add+=c;//wa点 这里是增加而不是赋值
tree[root].sum+=c;
return ;
}
pushdown(root,tree);
ll mid=(tree[root].l+tree[root].r)>>;
if(right<=mid)
updata(root<<,left,right,c,tree);
else
{
if(left>mid)
updata(root<<|,left,right,c,tree);
else
{
updata(root<<,left,mid,c,tree);
updata(root<<|,mid+,right,c,tree);
}
}
pushup(root,tree);
}
ll poww(ll n,ll m)
{
ll ans = ;
while(m > )
{
if(m & )ans = (ans * n) % mod;
m = m >> ;
n = (n * n) % mod;
}
return ans%mod;
}
ll n,q;
char what;
ll l1,r1,ad;
int main()
{
int t;
cin>>t;
while(t--)
{
scanf("%lld %lld",&n,&q);
buildtree(,,n,tree1);
buildtree(,,n,tree2);
while(q--)
{
scanf("%lld %lld %lld",&l1,&r1,&ad);
if(ad==)
{
updata(,l1,r1,,tree1);
}
else if(ad==)
{
updata(,l1,r1,,tree2);
}
}
cout<<poww(,tree1[].sum)*poww(,tree2[].sum)%mod<<endl;
}
return ;
}
最新文章
- HTML中id、name、class 区别
- new一个Object对象占用多少内存?
- vc 实现打印功能
- h5上滑刷新(分页)
- Windows Store App 应用程序存储空间
- java学习之(接口)
- POJ 3026 Borg Maze
- poj1273--Drainage Ditches(最大流Edmond-Karp算法 邻接表实现)
- JY05-JavsScript-JS基础01
- HDU 3032 Nim or not Nim? (sg函数求解)
- burp插件开发
- SpringMVC简单入门
- PHPMailer <; 5.2.21 - Local File Disclosure(CVE-2017-5223)
- sso示例代码
- C# MongoDB
- 三、调试IIS启动域名配置
- List Leave
- 2017.07.06【NOIP提高组】模拟赛B组
- (实用)pip源
- html5 随机数函数