牛客寒训营3 I(尺取或二分，做麻烦了)

题目 题意: 给定一个字符串，求所有长度在[L,R]之间满足条件的字符串。条件为:四个类别的字符中至少有三个。①小写字母②大写字母③数字④特殊字符 思路: 我总结对于每个位置去二分最右边的合法位置，统计满足长度的贡献。因为维护了四个类型的前缀和，这样是O(nlogn)的。  但是看了一手题解，发现可以O(n)。不需要维护四个类型的前缀和，直接开长度为4的数组就能维护每个类型字母最右边的位置。然后sort一下就可以找到最右边的合法位置。O(n * 4 log(4)),O(n). 时间复杂度: O(n) 代码:

赛时代码

// Problem: 智乃的密码
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/23478/I
// Memory Limit: 524288 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define OldTomato ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr)
#define fir(i,a,b) for(int i=a;i