4.4 省选模拟赛 拉格朗日计数 树状数组+容斥.

像这种计数 问题什么的 是最讨厌的了...

考虑是环往环后面再续一段 暴力枚举前两个数字 树状数组统计第三个数的个数 n^2log.

考虑只枚举第个数 发现由于边界问题什么的很难处理。

再将枚举直接放到环上 发现边界问题没有了 不过存在 枚举第二个数之后 有 123 231 312 这三种形式。

第一种形式很好统计 预处理一下左边有多少个数字比自己小即可。

考虑第二种和第三种形式 很难在枚举2的时候统计出来这两种形式 考虑容斥 231=XX1-321. 312=3XX-321.

发现XX1和3XX很好统计 321和上述123一样的统计方式 即可O(nlogn)得到答案。

const int MAXN=200010;
int n,T,m,top;ll ans=0;
int a[MAXN],c[MAXN];ll f[MAXN];
inline void add(int x,int y){while(x<=n){c[x]+=y;x+=x&(-x);}}
inline int ask(int x){int cnt=0;while(x){cnt+=c[x];x-=x&(-x);}return cnt;}
signed main()
{
	freopen("1.in","r",stdin);
	get(n);
	rep(1,n,i)
	{
		get(a[i]);
		f[i]=ask(a[i]-1);
		add(a[i],1);
	}
	rep(1,n,i)
	{
		ans+=f[i]*(n-i-(a[i]-1-f[i]));//123 左边比我小 右边比我大
		ans+=(a[i]-1-f[i])*(a[i]-1-f[i]-1)/2;//3XX
		ans+=(i-1-f[i])*(i-1-f[i]-1)/2;//XX1
		ans-=(i-1-f[i])*(a[i]-1-f[i])*2;//左边比我大 右边比我小
	}
	putl(ans);return 0;
}

原文地址:https://www.cnblogs.com/chdy/p/12632918.html

时间: 04-03

4.4 省选模拟赛 拉格朗日计数 树状数组+容斥.的相关文章

4.15 省选模拟赛 编码 trie树 前缀和优化建图 2-sat

好题 np. 对于20分 显然可以爆搜. 对于50分 可以发现每个字符串上的问号要么是0,要么是1.考虑枚举一个字符串当前是0还是1 这会和其他字符串产生矛盾. 所以容易 发现这是一个2-sat问题. 拆点 把任意两个产生矛盾的字符串进行连边.然后最后判矛盾即可. n^2枚举 建图 判断矛盾时使用字符串hash 要分类讨论4种情况. using namespace std; const int MAXN=1010,maxn=500010,cc1=19260817,cc2=114514; int

[USACO17JAN] Promotion Counting晋升者计数 (树状数组+dfs)

题目大意:给你一棵树,求以某节点为根的子树中,权值大于该节点权值的节点数 本题考查dfs的性质 离散+树状数组求逆序对 先离散 我们发现,求逆序对时,某节点的兄弟节点会干扰答案 所以,我们在递推时统计一次答案,递归时再统计一次答案,两者的差值就是最终结果 #include <bits/stdc++.h> #define dd double #define N 100100 using namespace std; int n,cnt,ma,lst; int a[N],head[N],s[N],

2018.3.10 省选模拟赛

从这里开始 概况 Problem A 三元组 Problem B 攻略 Problem C 迂回 概况 这是省选T1合集?还是欢乐AK赛? 全班一半以上的人三道题都会做qwq. Doggu还剩一小时时以为自己AK了,然后玩了一小时.虽然最终被卡了20分的常数. ZJC 1个半小时AK?Excuse me? 我这条大咸鱼到最后10分钟才敲完了T1,然后发现线段树要T掉. 发自内心鄙视垃圾出题人卡常数,本来的欢乐AK变成280. 教练给我们考4个小时的试,题面上也这么写的,看题解,woc,考试时间3

2018/3/29 省选模拟赛 80

我真是太菜了... T1 10分纯暴力没写,20分容斥也没写(人就是懒死的).还有30分矩乘不会 正解 <IOI2018 中国国家集训队第一阶段作业题解部分 - 杭州第二中学 吴瑾昭.pdf>最后一题 T2  以为自己能拿到50分,但是其实那个暴力算法只能过10分的点,n=2000的20分数据用n^3带剪枝过不了,所以拿了30分. 正解 <计数与期望问题选讲 CLJ.pdf>最后一题 我记得我以前好像看到过这个文档但是没读过..今天读一下 T3 依然是分情况50分,30分树归20分

【2018.12.15】【考试总结】【模拟+逆序对+树状数组+贪心+multiset】爆零之旅

这是我悲惨的接近爆零的一次考试,但是本蒟蒻不能放弃,还是要总结的QAQ 答题卡 [题目背景] 八月是个悲惨的月份.先不谈炎热的天气,对于新生来说,八月意味着军训: 而对于高二高三的同学来说,八月意味着开学考试.而考试就意味着改卷,改卷 也就意味着答题卡.不幸的是,学校读答题卡的机器的评分软件坏了,wyx 就被 老师要求写一个评分的程序. [问题描述] 软件需要读入学生的姓名.试题答案以及学生的答题卡信息. 学生姓名 学校的信息管理系统中存储了所有学生的姓名,一共 名学生.每个学生的 名字的组成只

Hdu 3887树状数组+模拟栈

题目链接 Counting Offspring Time Limit: 15000/5000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 1757    Accepted Submission(s): 582 Problem Description You are given a tree, it’s root is p, and the node is numbered fr

13杭州区域赛现场赛Rabbit Kingdom(树状数组+离线)

题意:给你一个长度数列,再给你m个询问(一个区间),问你在这个区间里面有多少个数与其他的数都互质. 解题思路:你看这种类型的题目都可以肯定这是 离线+树状数组(线段树).主要就是他的更新信息.这里我的处理是先把1-200000(每个数的范围)数里面所有的质因子求出来.然后从后往前遍历数组.会出现以下几种情况 1.a[k]的质因子在后面出现过而[更新标记] 和[被更新标记] 都为假 2.a[k]的质因子在后面出现过的那个位置 I   [更新标记]为 真 . 3.a[k]的质因子在后面出现过且那个位

Codeforces 216D Spider&#39;s Web 树状数组+模拟

题目链接:http://codeforces.com/problemset/problem/216/D 题意: 对于一个梯形区域,如果梯形左边的点数!=梯形右边的点数,那么这个梯形为红色,否则为绿色, 问: 给定的蜘蛛网中有多少个红色. 2个树状数组维护2个线段.然后暴力模拟一下,因为点数很多但需要用到的线段树只有3条,所以类似滚动数组的思想优化内存. #include<stdio.h> #include<iostream> #include<string.h> #in

PAT甲题题解-1095. Cars on Campus(30)-(map+树状数组,或者模拟)

题意:给出n个车辆进出校园的记录,以及k个时间点,让你回答每个时间点校园内的车辆数,最后输出在校园内停留的总时间最长的车牌号和停留时间,如果不止一个,车牌号按字典序输出. 几个注意点: 1.如果一个车连续多次进入,只取最后一个 2.如果一个车连续多次出去,只取第一个 3.一个车可能出入校园内好几次,停留时间取总和 实际上题目就是让我们求某个时间段内的车辆总和,时间段其实就相当于一个区间,区间求和的话,很快就联想到树状数组和线段树.然而怎么将时间段和区间联系起来呢,那就存储出现在记录和询问里的所有