NOI online 2022 游记
cool_milo
·
·
个人记录
CQOI2022 rp++;
凯 旋 归 来
考试开始前一直进不去系统，发现自己进的是普及组，然后去世了。
正序开题
首先计划把 T1-T3 先全部看一遍，然后发现 T1 非常可做，
于是不往下看了。
Problem1
~~题目名字也很好~~
发现每个数据产生贡献，一定是在一个连续的区间里，然后想如果把这个区间修改就行了。
打着打着发现不太对，好像计算重复了，于是停了下来，~~想起之前在线很难的问题是怎么离线水掉的~~。
于是转而考虑离线，发现碰到区间的左端点看成修改，好像就能处理询问了。大概就是说在 $w_i$ 的位置让 $a_i$++，对于每一组询问 $(l,r)$在$l$位置查询$r$就行了，树状数组$O(nlogn)$查询。
```cpp
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
//我悟了
const int N=5e5+5;
int n,a[N],b[N],upd[N],l,r,q,cnt,ans[N];
int stk[N],top;
int tr[N];
struct que{
int type;//2,1,0
int idx,r;
int l,pos,t;//在pos加上t
int ans;
}query[N<<2];
bool cmp1(que a,que b)
{
if(a.l != b.l)
return a.l < b.l;
return a.type < b.type;
}
void modify(int l,int v)
{
for(int i=l;i<=n;i+= i &(-i))
tr[i] += v;
}
int check(int l)
{
int ans = 0;
for(int i=l;i;i-= i & (-i))
ans += tr[i];
return ans;
}
inline void read(int &x)
{
char c = ' ';
while(!isalnum(c)) c = getchar();
while(isalnum(c))
{
x *= 10;
x += c - '0';
c = getchar();
}
}
inline void print(int x)
{
int t = 0;
int c[10];
while(x)
{
t++;
c[t] = x % 10;
x /= 10;
}
for(int i=t;i>=1;i--)
putchar(c[i] + '0');
putchar('\n');
}
int main()
{
freopen("stack.in","r",stdin);
freopen("stack.out","w",stdout);
read(n),read(q);
for(int i=1;i<=n;i++)
read(a[i]);
for(int i=1;i<=n;i++)
read(b[i]);
for(int i=1;i<=n;i++)
{
while(top && (a[stk[top]] == a[i] || b[stk[top]] <= b[i])) top--;
upd[i] = stk[top];
stk[++top] = i;
//依葫芦画瓢
}
for(int i=1;i<=n;i++)
{
query[++cnt] = {0,q+1,0,upd[i] + 1,i,1,0};
query[++cnt] = {2,q+1,0,i,i,-1,0};
}
for(int i=1;i<=q;i++)
{
l = r = 0;
read(l);
read(r);
query[++cnt] = {1,i,r,l,0,0,0};
}
sort(query+1,query+cnt+1,cmp1);
for(int i=1;i<=cnt;i++)
{
if(query[i].type == 1)
ans[query[i].idx] = check(query[i].r);
else
modify(query[i].pos,query[i].t);
}
for(int i=1;i<=q;i++)
print(ans[i]);
return 0;
}
```
##### 花絮：
打完跑大样栗 $2.6s$，慌得一批。
+ 快读，1.7s
+ 快写，1.001s(不做人了直接）
+ 大喊一声：万水千山总是情，少跑一秒行不行
+ 想到一个卡常，改完后0.85s
+ 洛谷极限数据0.3s
$Problem2
开始没什么思路，于是出去想了一会。
一看就是带负常数的$log$。
已知带负常数的做法只有两种：并查集，树状数组。
~~由抽屉原理得~~，刚才用过树状数组，现在只能是并查集。
~~就这么想出了正解~~
大概就是把“会做题的集合”从小到大排序，把每个“集合”在并查集上合并起来。
如果发现额外合并了元素，那么就能知道是之前合并起来的，所以得知那个额外合并获得的地方就是那个“不重复的地方”，拿出来就是了。
```cpp
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+5;
int T,n,k,tmp,flag,ans1,ans2;
vector<int> vc[N];
//nlogn shui 1e6!!!
int fa[N],sz[N],tub[N],fr[N];//并查集yyds
int find(int x)
{
if(fa[x] == x)
return x;
return fa[x] = find(fa[x]);
}
inline void read(int &x)
{
// char c = ' ';
// x = 0;
// while(!isalnum(c)) c = getchar();
// while(isalnum(c))
// {
// x *= 10;
// x += c - '0';
// c = getchar();
// }
scanf("%d",&x);
}
inline void print(int x)
{
int t = 0;
int c[10];
while(x)
{
t++;
c[t] = x % 10;
x /= 10;
}
for(int i=t;i>=1;i--)
putchar(c[i] + '0');
putchar('\n');
}//ssd yyds
bool cmp(vector<int> a,vector<int> b)
{
return a.size() < b.size();
}
int main()
{
freopen("discuss.in","r",stdin);
freopen("discuss.out","w",stdout);
cin>>T;
while(T--)
{
ans1 = ans2 = 0;
scanf("%d",&n);
for(int i=1;i<=n;i++)
vc[i].clear();
flag = false;
for(int i=1;i<=n;i++)
{
vc[i].clear();
vc[i].push_back(i);
scanf("%d",&k);
for(int j=1;j<=k;j++)
{
scanf("%d",&tmp);
vc[i].push_back(tmp);
}
}
sort(vc+1,vc+n+1,cmp);
for(int i=1;i<=n;i++)
fa[i] = i,sz[i] = 1,tub[i] = 0,fr[i] = 0;
for(int i=1;i<=n;i++)
{
if(vc[i].size() > 1)
{
tmp = find(vc[i][1]);
fr[vc[i][1]] = i;
}
for(int j=2;j<(int)vc[i].size();j++)
{
int a = find(vc[i][j]);//合并合并！全部合并！
fr[vc[i][j]] = i;
if(a == tmp) continue;
fa[a] = tmp;
sz[tmp] += sz[a];
}
if((vc[i].size() > 1) && sz[tmp] != ((int)vc[i].size())- 1)
{
flag = true;
ans1 = i;
break;
}
}
if(!flag)
puts("NO");
else
{
puts("YES");
for(int i=1;i<(int)vc[ans1].size();i++)
{
tub[vc[ans1][i]] = true;
//cout<<vc[ans1][i]<<endl;
}
for(int i=1;i<=n;i++)
{
if(find(i) == tmp && !tub[i])
ans2 = fr[i];
}
printf("%d ",vc[ans1][0]);
print(vc[ans2][0]);
}
}
return 0;
}
```
------------
写完还有$90min
测大样栗的时候死活RE，检查了半天发现是输入错了，再检查：？？？？？？？这这不对吧是谁要陷害我？€€£你要陷害我是不是？
《于是调了90min输入》
11:59无可奈何地交了依旧RE的代码。
前方高能 前方高能 前方高能 非战斗人员请迅速撤离
考完马上知道：大样栗锅了！
我那胎死腹中的T3
拿着新来的大样栗测一测，马上就AC了。
@CCF_NOI讨说法
花絮2
1:15知道洛谷有冥间数据。测T2时非常自信的大喊了一声：我不开O2!
真香。
巨佬们的情况
@L_h_写出T1，文件操作写错了
@tanyulin主席树写出T1（orz!）加上骗分有130。自测发现UB了，默哀。
@duanyixiu炸掉了；
@yanghanyv的主席树顺利通关，orz！
@Sheng_horizon不仅T1和我想的一样，还自创了丹钓战的新写法，orz！
@MichaelLee的倍增大家都没懂，但是他也过了T1，orz！
Chery自然是AK了（）
但是 @Sword_K炸了，，，
默哀。
冲进前25%！好像完全没有问题
upd on 3/31/2022
出分了，没挂分，CCF nb，希望 CQYZ 以后还能再次辉煌。