网站开发与网页后台开发,江苏交通厅门户网站建设工程,百度公司全称叫什么,行业网站妄想集合(牛客练习赛90)
题意#xff1a;
开始有 n 个可重集合#xff0c;开始时每一个集合中都有一个数#xff0c;有 m 个操作。 Quant l r x\text{Quant l r x}Quant l r x#xff1a;往编号在 l∼rl\sim rl∼r 的每个集合中加入一个数 x。 Ask l r\text{Ask l r}Ask …妄想集合(牛客练习赛90)
题意
开始有 n 个可重集合开始时每一个集合中都有一个数有 m 个操作。
Quant l r x\text{Quant l r x}Quant l r x往编号在 l∼rl\sim rl∼r 的每个集合中加入一个数 x。 Ask l r\text{Ask l r}Ask l r询问能否从 l∼rl\sim rl∼r的集合中取出三个数使得他们能作为边长组成一个三角形即最小两个和要大于最大的。 1n,m1e5 所有数1e9
题解
一开始在想如何快速判断边长能否组成三角形,陷入了死胡同里后来在队友一说才想起来不能组成三角形的情况就是斐波那契而数列。 以前有遇到过一个最大的集合无法组成三角形那么这个集合中的元素为112356…就是斐波那契数列而都知道这个数列增长是否快的到1e9以内最多也才40多个也就是说如果一个区间内元素个数大于上限(我们将上限lim定为60)直接就是Yes修改时也只需要修改元素个数小于lim的集合即可 判断的时候只要集合内元素大于lim就是Yes如果小于我们就直接硬判断即可因为一共才不到60个数 复杂度:O(n∗logn∗60)O(n*logn*60)O(n∗logn∗60)
代码
#include bits/stdc.h
#include unordered_map
#define debug(a, b) printf(%s %d\n, a, b);
#define Memory() printf(%.2lfMB\n,(Most-Handsome)/1024.0/1024.0);
using namespace std;
bool Handsome;
typedef long long ll;
typedef unsigned long long ull;
typedef pairint, int PII;
clock_t startTime, endTime;
//Fe~Jozky
const ll INF_ll 1e18;
const int INF_int 0x3f3f3f3f;
void read(){};
template typename _Tp, typename... _Tps void read(_Tp x, _Tps... Ar)
{x 0;char c getchar();bool flag 0;while (c 0 || c 9)flag| (c -), c getchar();while (c 0 c 9)x (x 3) (x 1) (c ^ 48), c getchar();if (flag)x -x;read(Ar...);
}
template typename T inline void write(T x)
{if (x 0) {x ~(x - 1);putchar(-);}if (x 9)write(x / 10);putchar(x % 10 0);
}
void rd_test()
{
#ifdef ONLINE_JUDGE
#elsestartTime clock ();freopen(data.in, r, stdin);
#endif
}
void Time_test()
{
#ifdef ONLINE_JUDGE
#elseendTime clock();printf(\nRun Time:%lfs\n, (double)(endTime - startTime) / CLOCKS_PER_SEC);
#endif
}
int n,m;
const int maxn1e59;
vectorintvec[maxn];
setintpos;
bool Most;
int main()
{//rd_test();cinnm;for(int i1;in;i){int x;cinx;vec[i].push_back(x);//每个集合pos.insert(i); }while(m--){string op;int l,r;cinoplr;if(opQuant){int x;cinx;setint::iterator itpos.lower_bound(l);while(it!pos.end()*itr){//对集合进行维护 vec[(*it)].push_back(x);if(vec[*it].size()60)pos.erase(it);else it; }}else {if(r-l160){puts(YES);continue;}vectorinttmp;for(int il;ir;i) tmp.insert(tmp.end(),vec[i].begin(),vec[i].end());sort(tmp.begin(),tmp.end());bool flag0;for(int i1;itmp.size()-1;i){if(tmp[i-1]tmp[i]tmp[i1]){puts(YES);flag1;break;}}if(!flag)puts(NO);}}return 0;//Time_test();
}
