hdu 5751 Eades

题意:对于整数序列$A[1...n]$定义$f(l, r)$为区间$[l, r]$内等于区间最大值元素的个数,定义$z[i]$为所有满足$f(l, r)=i$的区间总数。对于所有的$1 \leq i \leq n$,计算$z[i]$。

分析:考虑由大往小枚举最大值,对于某一最大值为$M$的区间$[l, r)$,满足$a[p_i]=M$的元素将区间切割为若干子区间,那么这些子区间对长度的积对答案的某一项有等值的贡献,暴力枚举需要$O(n^2)$的时间,整体考虑那些对答案某一项有贡献的子区间对的积,它们满足卷积的性质。因此只需将长度序列与其反序列作类似多项式乘法的fft,即可将时间优化为$O(nlog(n))$。子区间递归处理即可。代码如下:

  1 #include <algorithm>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <string>
  5 #include <queue>
  6 #include <map>
  7 #include <set>
  8 #include <stack>
  9 #include <ctime>
 10 #include <cmath>
 11 #include <iostream>
 12 #include <assert.h>
 13 #pragma comment(linker, "/STACK:102400000,102400000")
 14 #define max(a, b) ((a) > (b) ? (a) : (b))
 15 #define min(a, b) ((a) < (b) ? (a) : (b))
 16 #define mp std :: make_pair
 17 #define st first
 18 #define nd second
 19 #define keyn (root->ch[1]->ch[0])
 20 #define lson (u << 1)
 21 #define rson (u << 1 | 1)
 22 #define pii std :: pair<int, int>
 23 #define pll pair<ll, ll>
 24 #define pb push_back
 25 #define type(x) __typeof(x.begin())
 26 #define foreach(i, j) for(type(j)i = j.begin(); i != j.end(); i++)
 27 #define FOR(i, s, t) for(int i = (s); i <= (t); i++)
 28 #define ROF(i, t, s) for(int i = (t); i >= (s); i--)
 29 #define dbg(x) std::cout << x << std::endl
 30 #define dbg2(x, y) std::cout << x << " " << y << std::endl
 31 #define clr(x, i) memset(x, (i), sizeof(x))
 32 #define maximize(x, y) x = max((x), (y))
 33 #define minimize(x, y) x = min((x), (y))
 34 using namespace std;
 35 typedef long long ll;
 36 const int int_inf = 0x3f3f3f3f;
 37 const ll ll_inf = 0x3f3f3f3f3f3f3f3f;
 38 const int INT_INF = (int)((1ll << 31) - 1);
 39 const double double_inf = 1e30;
 40 const double eps = 1e-14;
 41 typedef unsigned long long ul;
 42 typedef unsigned int ui;
 43 inline int readint(){
 44     int x;
 45     scanf("%d", &x);
 46     return x;
 47 }
 48 inline int readstr(char *s){
 49     scanf("%s", s);
 50     return strlen(s);
 51 }
 52
 53 class cmpt{
 54 public:
 55     bool operator () (const int &x, const int &y) const{
 56         return x > y;
 57     }
 58 };
 59
 60 int Rand(int x, int o){
 61     //if o set, return [1, x], else return [0, x - 1]
 62     if(!x) return 0;
 63     int tem = (int)((double)rand() / RAND_MAX * x) % x;
 64     return o ? tem + 1 : tem;
 65 }
 66 void data_gen(){
 67     srand(time(0));
 68     freopen("in.txt", "w", stdout);
 69     int kases = 20;
 70     printf("%d\n", kases);
 71     while(kases--){
 72         int sz = 6e4;
 73         printf("%d\n", sz);
 74         FOR(i, 1, sz) printf("%d ", Rand(sz, 1));
 75         printf("\n");
 76     }
 77 }
 78
 79 struct cmpx{
 80     bool operator () (int x, int y) { return x > y; }
 81 };
 82 const int maxn = 6e4 + 10;
 83 int a[maxn];
 84 int n;
 85 struct Seg{
 86     int l, r, v;
 87 }seg[maxn << 2];
 88 void build(int u, int l, int r){
 89     seg[u].l = l, seg[u].r = r;
 90     if(seg[u].r - seg[u].l < 2){
 91         seg[u].v = l;
 92         return;
 93     }
 94     int mid = (l + r) >> 1;
 95     build(lson, l, mid), build(rson, mid, r);
 96     if(a[seg[rson].v] > a[seg[lson].v]) seg[u].v = seg[rson].v;
 97     else seg[u].v = seg[lson].v;
 98 }
 99 int query(int u, int l, int r){
100     if(seg[u].l == l && seg[u].r == r) return seg[u].v;
101     int mid = (seg[u].l + seg[u].r) >> 1;
102     if(r <= mid) return query(lson, l, r);
103     else if(l >= mid) return query(rson, l, r);
104     int lhs = query(lson, l, mid), rhs = query(rson, mid, r);
105     if(a[rhs] > a[lhs]) return rhs;
106     return lhs;
107 }
108 int maxi;
109 vector<int> pos[maxn];
110 int idx[maxn];
111 void init(){
112     maxi = -1;
113     FOR(i, 1, n) maximize(maxi, a[i]);
114     FOR(i, 1, maxi) pos[i].clear();
115     FOR(i, 1, n){
116         int sz = pos[a[i]].size();
117         idx[i] = sz;
118         pos[a[i]].pb(i);
119     }
120 }
121 ll z[maxn];
122 ll c[maxn], d[maxn], e[maxn << 1];
123 int k;
124 const double PI = 2 * asin(1.);
125 struct Complex{
126     double x, y;
127     Complex(double x = 0, double y = 0) : x(x), y(y) {}
128 };
129 Complex operator + (const Complex &lhs, const Complex &rhs){
130     return Complex(lhs.x + rhs.x, lhs.y + rhs.y);
131 }
132 Complex operator - (const Complex &lhs, const Complex &rhs){
133     return Complex(lhs.x - rhs.x, lhs.y - rhs.y);
134 }
135 Complex operator * (const Complex &lhs, const Complex &rhs){
136     double tl = lhs.x * rhs.x, tr = lhs.y * rhs.y, tt = (lhs.x + lhs.y) * (rhs.x + rhs.y);
137     return Complex(lhs.x * rhs.x - lhs.y * rhs.y, lhs.x * rhs.y + lhs.y * rhs.x);
138 }
139 Complex w[2][maxn << 2], x[maxn << 2], y[maxn << 2];
140
141 void fft(Complex x[], int k, int v){
142     int i, j, l;
143     Complex tem;
144     for(i = j = 0; i < k; i++){
145         if(i > j) tem = x[i], x[i] = x[j], x[j] = tem;
146         for(l = k >> 1; (j ^= l) < l; l >>= 1) ;
147     }
148     for(i = 2; i <= k; i <<= 1) for(j = 0; j < k; j += i) for(l = 0; l < i >> 1; l++){
149         tem = x[j + l + (i >> 1)] * w[v][k / i * l];
150         x[j + l + (i >> 1)] = x[j + l] - tem;
151         x[j + l] = x[j + l] + tem;
152     }
153 }
154 int tot;
155 void solve(int l, int r){
156     if(l >= r) return;
157     if(r - l == 1){
158         ++z[1];
159         return;
160     }
161     int p = query(1, l, r);
162     int tem = idx[p];
163     int sz = pos[a[p]].size();
164     k = 0;
165     c[k++] = p - l + 1;
166     while(tem  + 1 < sz && pos[a[p]][tem + 1] < r) c[k++] = pos[a[p]][tem + 1] - pos[a[p]][tem], ++tem;
167     c[k++] = r - pos[a[p]][tem];
168     ROF(i, k - 1, 0) d[i] = c[k - 1 - i];
169     int len;
170     for(len = 1; len < (k << 1); len <<= 1) ;
171     FOR(i, 0, len) w[1][len - i] = w[0][i] = Complex(cos(PI * 2 * i / len), sin(PI * 2 * i / len));
172     FOR(i, 0, k - 1) x[i] = Complex(c[i], 0);
173     FOR(i, k, len - 1) x[i] = Complex(0, 0);
174     fft(x, len, 0);
175     FOR(i, 0, k - 1) y[i] = Complex(d[i], 0);
176     FOR(i, k, len - 1) y[i] = Complex(0, 0);
177     fft(y, len, 0);
178     FOR(i, 0, len - 1) x[i] = x[i] * y[i];
179     fft(x, len, 1);
180     FOR(i, 0, 2 * k - 2) e[i] = (ll)(x[i].x / len + .5);
181     FOR(i, 0, k - 2) z[k - 1 - i] += e[i];
182     tem = idx[p];
183     solve(l, p);
184     while(tem + 1 < sz && pos[a[p]][tem + 1] < r) solve(pos[a[p]][tem] + 1, pos[a[p]][tem + 1]), ++tem;
185     solve(pos[a[p]][tem] + 1, r);
186 }
187 int main(){
188     //data_gen(); return 0;
189     //C(); return 0;
190     int debug = 0;
191     if(debug) freopen("in.txt", "r", stdin);
192     //freopen("out.txt", "w", stdout);
193     int T = readint();
194     while(T--){
195         n = readint();
196         FOR(i, 1, n) a[i] = readint();
197         build(1, 1, n + 1);
198         init();
199         clr(z, 0);
200         tot = 0;
201         solve(1, n + 1);
202         ll ans = 0;
203         FOR(i, 1, n) ans += z[i] ^ i;
204         printf("%lld\n", ans);
205     }
206     return 0;
207 }

code:

时间: 08-15

hdu 5751 Eades的相关文章

HDU 6203 ping ping ping [LCA,贪心,DFS序,BIT(树状数组)]

题目链接:[http://acm.hdu.edu.cn/showproblem.php?pid=6203] 题意 :给出一棵树,如果(a,b)路径上有坏点,那么(a,b)之间不联通,给出一些不联通的点对,然后判断最少有多少个坏点. 题解 :求每个点对的LCA,然后根据LCA的深度排序.从LCA最深的点对开始,如果a或者b点已经有点被标记了,那么continue,否者标记(a,b)LCA的子树每个顶点加1. #include<Bits/stdc++.h> using namespace std;

HDU 5542 The Battle of Chibi dp+树状数组

题目:http://acm.hdu.edu.cn/showproblem.php?pid=5542 题意:给你n个数,求其中上升子序列长度为m的个数 可以考虑用dp[i][j]表示以a[i]结尾的长度为j的上升子序列有多少 裸的dp是o(n2m) 所以需要优化 我们可以发现dp的第3维是找比它小的数,那么就可以用树状数组来找 这样就可以降低复杂度 #include<iostream> #include<cstdio> #include<cstring> #include

hdu 1207 汉诺塔II (DP+递推)

汉诺塔II Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 4529    Accepted Submission(s): 2231 Problem Description 经典的汉诺塔问题经常作为一个递归的经典例题存在.可能有人并不知道汉诺塔问题的典故.汉诺塔来源于印度传说的一个故事,上帝创造世界时作了三根金刚石柱子,在一根柱子上从下往

[hdu 2102]bfs+注意INF

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2102 感觉这个题非常水,结果一直WA,最后发现居然是0x3f3f3f3f不够大导致的--把INF改成INF+INF就过了. #include<bits/stdc++.h> using namespace std; bool vis[2][15][15]; char s[2][15][15]; const int INF=0x3f3f3f3f; const int fx[]={0,0,1,-1};

HDU 3555 Bomb (数位DP)

数位dp,主要用来解决统计满足某类特殊关系或有某些特点的区间内的数的个数,它是按位来进行计数统计的,可以保存子状态,速度较快.数位dp做多了后,套路基本上都差不多,关键把要保存的状态给抽象出来,保存下来. 简介: 顾名思义,所谓的数位DP就是按照数字的个,十,百,千--位数进行的DP.数位DP的题目有着非常明显的性质: 询问[l,r]的区间内,有多少的数字满足某个性质 做法根据前缀和的思想,求出[0,l-1]和[0,r]中满足性质的数的个数,然后相减即可. 算法核心: 关于数位DP,貌似写法还是

HDU 5917 Instability ramsey定理

http://acm.hdu.edu.cn/showproblem.php?pid=5917 即世界上任意6个人中,总有3个人相互认识,或互相皆不认识. 所以子集 >= 6的一定是合法的. 然后总的子集数目是2^n,减去不合法的,暴力枚举即可. 选了1个肯定不合法,2个也是,3个的话C(n, 3)枚举判断,C(n, 4), C(n, 5) #include <bits/stdc++.h> #define IOS ios::sync_with_stdio(false) using name

hdu 6166 Senior Pan

地址:http://acm.split.hdu.edu.cn/showproblem.php?pid=6166 题目: Senior Pan Time Limit: 12000/6000 MS (Java/Others)    Memory Limit: 131072/131072 K (Java/Others)Total Submission(s): 245    Accepted Submission(s): 71 Problem Description Senior Pan fails i

2017中国大学生程序设计竞赛 - 网络选拔赛 HDU 6155 Subsequence Count 矩阵快速幂

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=6155 题意: 题解来自:http://www.cnblogs.com/iRedBean/p/7398272.html 先考虑dp求01串的不同子序列的个数. dp[i][j]表示用前i个字符组成的以j为结尾的01串个数. 如果第i个字符为0,则dp[i][0] = dp[i-1][1] + dp[i-1][0] + 1,dp[i][1] = dp[i-1][1] 如果第i个字符为1,则dp[i][1

HDU 1513 Palindrome:LCS(最长公共子序列)or 记忆化搜索

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1513 题意: 给你一个字符串s,你可以在s中的任意位置添加任意字符,问你将s变成一个回文串最少需要添加字符的个数. 题解1(LCS): 很神奇的做法. 先求s和s的反串的LCS,也就是原串中已经满足回文性质的字符个数. 然后要变成回文串的话,只需要为剩下的每个落单的字符,相应地插入一个和它相同的字符即可. 所以答案是:s.size()-LCS(s,rev(s)) 另外,求LCS时只会用到lcs[i-