CF455E Function

2022-09-22 20:02:40 字數 1379 閱讀 3166

cf455e function

按照題意模擬容易發現,這玩意就是在 \([r - l, r]\) 區間內可重複選擇數字求最小值,但是有個特殊要求也就是如果,你從 \(i\) 開始選,那麼 \([i, r]\) 都必須至少選 \(1\) 個。

容易發現,肯定儘量重複選小的 \(val_i\)。也就是答案是 \(s_r - s_i + (l-r+i) \cdot a_i\)。(\(s\) 為字首和。)

然後可以知道 \(i\) 一定是 \([r-l, r]\) 區間中最小的。

當 \(i \lt j\) 時,並且選 \(i\) 比選 \(j\) 更優秀。

那麼 \(s_r - s_i + (l - r + i) \cdot a_i \le s_r - s_j + (l - r + j) \cdot a_j\)

\((l-r)(a_i-a_j) \lt (s_i - i \cdot a_i) - (s_j - j \cdot a_j)\)

整理可以得到 \(l - r \gt \dfrac\)

注意 \(a_i \lt a_j\)。

然後就維護一個凸包(單調棧維護)。

因為斜率不單調,所以不能用單調佇列。

每次找到起點,終點,然後二分斜率隨便做。

/*

name: cf455e

author: gensokyo_alice

date: 2020/11/17

description:

*/#include #include #include #include #include #include #include #include #include #include #include #include using namespace std;

typedef long long ll;

const ll maxn = 1e6+10;

ll val[maxn], s[maxn], n, m, ans[maxn], top, st[maxn];

struct que

} q[maxn];

double slp(ll, ll);

ll find_(ll);

int main()

rb = q[j].y, lb = st[lb];

ans[q[j].id] = s[rb] - s[lb] + (q[j].x - rb + lb) * val[lb];

j++;

} }for (ll i = 1; i <= m; i++) printf("%lld\n", ans[i]);

return 0;

}double slp(ll i, ll j)

ll find_(ll x)

return l;

}

CF163E e Government

題目 兩個 log 的樹狀陣列套樹剖? 我們對於給出的 n 個模式串建立 ac 自動機,之後對於每一個詢問串直接丟上去匹配 如果這裡是暴力的...

CF163E e Government

題面傳送門 像這種多字串匹配就可以考慮建出ac自動機來搞。 如果沒有增刪操作直接匹配即可。 但是這道題有增刪操作。每個節點fail子樹內的權值會變。 所以可以把fail樹的dfs序跑出來在上面維護樹狀陣列即可。 講道理這道題詢問很多修改很少應該套分塊才是,但是出題人沒卡就不管了 時間複雜度 o s...

CF163E e Government

點這裡看題目。 首先,我們不需要真的從 ac 自動機中把串刪掉。由於我們計算貢獻和,我們只需要在 ac 自動機上,把已經刪除的串的貢獻抹掉就可以了。 接著考慮詢問。這是一個很基礎的問題,一般我們會在 ac 自動機上面處理出每個狀態的貢獻和,並且將詢問的字串在 ac 自動機上面跑一跑,答案就是經過的...