正文

{CodeForces】788E New task && 汕头市队赛SRM06 D 五色战队

IP云
IP云V管理员/3 阅读
09/21
提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

D 五色战队 SRM 06

背景&&描述

        游行寺家里人们的发色多种多样，有基佬紫、原谅绿、少女粉、高级黑、相簿白等。
        日向彼方：吾令人观其气，气成五彩，此天子气也。
        琉璃：我们是不是可以组个五人战队了？
        游行寺家的n个人排成一排。第i个人的发色是Ai。
        能组成战队的条件是：
                那五人假设是第a,b,c,d,e人()，需要满足 
                中间的三人称为有头者，最旁边俩人称为学姐。
                根据字面意思，有头者一定要有头，学姐可以无头。
                反正就是b,c,d这三人一定要有头。
        有着恶趣味的琉璃每次操作会把一个人 变成有头或者无头，
        每次操作后琉璃想知道游行寺家可能产生多少种不同的战队。只要有成员不同,俩战队就是不同的。
 

输入格式

第一行一个整数n，第二行n个整数表示人们的发色。

第三行一个整数m，表示操作数。

接下来有m行，每行第一个数表示操作类型，第二个数表示被操作那人的编号。

类型为1就是把他变无头，类型2就是变有头。

输出格式

每次操作后输出答案，答案对10^9+7取模。。。

样例输入

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

样例输出

1
6
2

数据范围与约定

  • 对于100%的数据:

样例解释

第一次操作后可能的战队为{1,2,3,7,8}

第二次操作后可能的战队为{1,2,3,5,7}，{1,2,3,5,8}，{1,2,3,7,8}，{1,2,5,7,8}，{1,3,5,7,8}，{2,3,5,7,8}。

第三次操作后可能的战队为{1,3,5,7,8}，{2,3,5,7,8}

这道题和codechef的原题差不多

题目要求的就是

n个数字中，每个数有数字A和属性B，每次操作将某个点x的属性B改变为0或1，求满足这样要求的子序列的个数：

下标a<b<c<d<e，而Aa<=Ab=Ac=Ad>=Ae且Bb=Bc=Bd=1。

那么每个数左边以及右边小于等于他的数 很显然我们可以用树状数组维护 下标就是值

当然为了方便我们需要将值离散化一波

这样之后 重点就是中间那三个数了 我们可以按值来搞 每个值建一棵线段树

需要维护的信息有（我们设五个点分别为 1 2 3 4 5

sz 及点的个数

A 就是 1 2

C 就是 2 3

AB就是 1 2 3

BC 就是 3 4 5

ABC 就是 1 2 3 4 5

具体怎么算看up咯

跟结点只需要算A C 而A C可以由左边比他小和右边比他小的点的数量得到 这样之后就简单多了 2333

#include<cstdio>
#include<cstring>
#include<algorithm>
#define LL long long
using namespace std;
const int M=,N=,mod=1e9+;
int read(){
int ans=,f=,c=getchar();
while(c<''||c>''){if(c=='-') f=-; c=getchar();}
while(c>=''&&c<=''){ans=ans*+(c-''); c=getchar();}
return ans*f;
}
int sum[N],s[N],ans;
struct node{int w,pos;}e[N];
bool cmp(node a,node b){return a.w<b.w;}
int n,m,cnt,sz;
int L[N],R[N],root[N];
void clear(){memset(sum,,sizeof(sum));}
int lowbit(int x){return x&-x;}
void add(int x){
while(x<=n){
sum[x]++;
x+=lowbit(x);
}
}
int push_sum(int x){
int ans=;
while(x){ans+=sum[x]; x-=lowbit(x);}
return ans;
}
struct note{
int l,r,sz;
int A,C,AB,BC,ABC;
}tr[M];
void up(int x){
int l=tr[x].l,r=tr[x].r;
tr[x].sz=(tr[l].sz+tr[r].sz)%mod;
tr[x].A=(tr[l].A+tr[r].A)%mod;
tr[x].C=(tr[l].C+tr[r].C)%mod;
tr[x].AB=(tr[l].AB+tr[r].AB+(LL)tr[l].A*tr[r].sz)%mod;
tr[x].BC=(tr[l].BC+tr[r].BC+(LL)tr[r].C*tr[l].sz)%mod;
tr[x].ABC=(tr[l].ABC+tr[r].ABC+(LL)tr[l].A*tr[r].BC+(LL)tr[l].AB*tr[r].C)%mod;
}
void mdf(int& x,int l,int r,int k,int v){
if(!x) x=++sz;
if(l==r){
tr[x].sz=*v;
tr[x].A=L[k]*v;
tr[x].C=R[k]*v;
tr[x].AB=tr[x].BC=tr[x].ABC=;
tr[x].l=tr[x].r=;
return ;
}
int mid=(l+r)>>;
if(k<=mid) mdf(tr[x].l,l,mid,k,v);
else mdf(tr[x].r,mid+,r,k,v);
up(x);
}
int main()
{
n=read();
for(int i=;i<=n;i++) e[i].w=read(),e[i].pos=i;
sort(e+,e++n,cmp);
for(int i=;i<=n;i++){
if(e[i].w!=e[i-].w) cnt++;
s[e[i].pos]=cnt;
}
clear();
for(int i=;i<=n;i++){
L[i]=push_sum(s[i]);
add(s[i]);
}
clear();
for(int i=n;i>=;i--){
R[i]=push_sum(s[i]);
add(s[i]);
}
for(int i=;i<=n;i++){
ans=(ans-tr[root[s[i]]].ABC+mod)%mod;
mdf(root[s[i]],,n,i,);
ans=(ans+tr[root[s[i]]].ABC)%mod;
}
int x,y;
m=read();
for(int i=;i<=m;i++){
x=read(); y=read();
ans=(ans-tr[root[s[y]]].ABC+mod)%mod;
mdf(root[s[y]],,n,y,x-);
ans=(ans+tr[root[s[y]]].ABC)%mod;
printf("%d\n",ans);
}
return ;
}

{CodeForces】788E New task && 汕头市队赛SRM06 D 五色战队的更多相关文章

  1. 汕头市队赛 C KMP codeforces B&period; Image Preview

    汕头市队赛题目传送门 codeforces题目传送门 这道题我的做法是 尝试先往左走然后往右走 或者先往右走然后往左走 然后注意一下枚举顺序就okay啦 #include<cstdio> ...

  2. 汕头市队赛SRM15

    T1——czl SRM 15 众所周知,czl家养了一只可♂爱的***(已屏蔽),那只东西很贪吃,所以czl家很多零食仓库,然而这些仓库里有很多老鼠. 为了心爱的***,czl决定点燃纯艾条,用烟熏老 ...

  3. Codeforces 788E - New task（线段树）

    Codeforces 题目传送门 & 洛谷题目传送门 这是一道 *2900 的 D1E,而且被!我!自!己!搞!出!来!了! 虽然我承认它难度及摆放的位置异常异常虚高,并且就算我到了现场也不可 ...

  4. 汕头市队赛 SRM 07 D 天才麻将少女kpm

    这道题放了很久还是回来补了 D 天才麻将少女KPM SRM 07 背景&&描述 天才麻将少女KPM立志要在日麻界闯出一番名堂.     KPM上周叒打了n场麻将,但她这次又没控分,而且 ...

  5. 汕头市队赛SRM 20 T3 灵魂觉醒

    背景 自从芽衣.布洛妮娅相继灵魂觉醒之后,琪亚娜坐不住了.自己可是第一个入驻休伯利安号的啊!于是她打算去找德丽莎帮忙,为她安排了灵魂觉醒的相关课程. 第一天,第一节课. “实现灵魂觉醒之前,你需要先将 ...

  6. 汕头市队赛SRM 20 T2不净的圣杯

    不净的圣杯 SRM 20 背景 作为一张BUG级别的卡,官方打算把它修改得人畜无害一些…… 虽然名字还没想好,但是能力大概是对敌方所有单位造成d点伤害,d为自己牌组中所有卡的编号的最大公约数.这无疑是 ...

  7. 汕头市队赛SRM 20 T1魔法弹

    T1 背景 “主角光环已经不能忍啦!” 被最强控制AP博丽灵梦虐了很长一段时间之后,众人决定联合反抗. 魂魄妖梦:“野怪好像被抢光了?” 十六夜咲夜:“没事,我们人多.” 然后当然是以失败告终了. 八 ...

  8. 汕头市队赛 SRM19 字符题

    从天上掉下来了个这样的问题: 有一个字符串 从中选出两个子串 A,B,求 A+B可以构成的不同串的个数. 还想知道,这么多个串中字典序最大的那一个. 某人捡到了这个问题,并把它扔给了你. [输入] 一 ...

  9. 汕头市队赛 SRM16 T2

    描述 猫和老鼠,看过吧?猫来了,老鼠要躲进洞里.在一条数轴上,一共有n个洞,位置分别在xi,能容纳vi只老鼠.一共有m只老鼠位置分别在Xi,要躲进洞里,问所有老鼠跑进洞里的距离总和最小是多少. 输入格 ...

随机推荐

  1. 20145330《Java程序设计》第一次实验报告

    20145330<Java程序设计>第一次实验报告 实验一Java开发环境的熟悉 实验内容 1.使用JDK编译.运行简单的Java程序: 2.使用Eclipse 编辑.编译.运行.调试Ja ...

  2. 对敏捷开发的误解（转自MBAlib）

    对敏捷开发的误解 误解一:敏捷对人的要求很高 很多人在尝试实施敏捷时说:敏捷对人的要求太高了,我们没有这样的条件,我们没有这样的人,因此我们没法敏捷.可是,敏捷对人的要求真的那么高么? 软件归根到底还 ...

  3. learn-python3

    # learn-python3   这是我初学Python时写的一套Python基础示例程序.主要基于廖雪峰老师的Python3教程和<<深入理解Python>>. 感谢! 下 ...

  4. Unity-layermask的问题

    using UnityEngine; using System.Collections; public class NewBehaviourScript : MonoBehaviour { priva ...

  5. wordpress搭建后地址栏页面显示IP地址的问题

    搭建了wordpress.也在万网加入了A记录,这时訪问站点(我的是yesareno.com),发现仅仅在yesareno的主页,地址栏是域名.点击进入其它界面发现地址栏变成了ip地址,例如以下图 竟 ...

  6. 《实战Java高并发程序设计》pdf

    花了我五元大洋,需要的拿去吧.百度云盘:https://pan.baidu.com/s/1o8bESY2

  7. tp框架 使用ajax

    <head> <meta http-equiv="Content-Type" content="text/html; charset=utf-8&quo ...

  8. Android开发艺术探究Note

    第一章:Activity的生命周期和启动模式 生命周期 onPause表示activity正在停止,onPaus必须先执行完(栈顶的activity),新的activity的onResume才会执行. ...

  9. c&num; 判断一个string&lbrack;&rsqb;是否全包含另一个string&lbrack;&rsqb;

    // list = normalList.Except(repairList).ToList(); //差集 // list = normalList.Union(repairList).ToList ...

  10. 实现我的第一个Java程序

    第一步.打开记事本 第二步.代码编写 public class Hello{ public static void main( String[] args){ System.out.println(& ...