小衣同学的博客

维护两个vector L、R，代表下一步要在[l,mid]和[mid+1,r]分治的vector。这样del里的元素，在并查集上找到其祖先时，可以用to数组确定其应该被放进L还是R。每次将x random_shuffle后，取出vector尾部的两个u、v，和已经被询问出来的元素再一起询问一次，就能确定出这个元素该放进L还是R。分治，假设当前解决到[l,r]，要递归的vector是x，期望次数是6000的，实际跑得飞快，也没被卡掉。只剩一个元素时，L或R一定已经有元素，首先特判n=1的情况，其实也不用问。

那么下一个位置区间，就是由当前位置区间l、r分别加上最慢速度lv、最快速度rv去生成，而历史每次询问出来的lp、rp，可以对lv、rv形成一个新的约束，最终收敛到lp=rp。询问的次数变多时，用限制条件去卡，速度实际是收敛的很快的。所以考虑二分位置p，用一个区间[lp,rp]去控制，100次，很容易想到是二分，但是check很难想。同样地，速度也用一个区间[lv,rv]去控制。两个未知量p、v，因为最后要求最终位置p，不是很能直观地证明，只是能大概感觉，

而一直问n-1显然肯定不行，这样会导致剩下的删边越来越多，最后剩下一堆小于n-2的。还会输出一个和这个点v当前没有连边的点x，如果x有多个，也输出点号最小的x。2. 如果问出来的是n-1，n-1可以和子图内的点任意连，插入到任何地方，1. 如果问出来的是n-2，显然删掉这个点的子图还满足这个条件，递归子图。交互题，n（n

（6）否则，记las的两个父亲为f1、f2（也就是上图的点6、点7），如果能往f1后面续，就往f1后面续，否则往f2后面续。新来的点3，可以接在点4后，也可以接在点5后，也可以接在点6后，也可以接在点7后，因为在链中间的点后面续新的点，都可以看成是在交点后面续新的点，不影响两条链的性质。而此时应该是10->9->6->3->2，另一条链8->7->5->4->1。而这种情况的出现，说明前面有一个只询问了1次的点，也就是在点5下面的点4，可以发现，在点5形成Y字型，后接点4之后，新来的点3并没有续到点4上，

令a[1]=huai,a[2]=huai+1，a[3]=huai+2，a[4]=hao，a[5]=hao+1,a[6]=hao+2，而a[2]和a[3]两坏情况是翻转不过来的，说明a[2]和a[3]只能是一好一坏，那么a[1]一定是坏。b[1]询问2、3、5，b[2]询问2、3、6，b[3]询问3，5，6，b[4]询问2、5、6。注意到a[1]-a[3]的询问结果是0，说明a[2]和a[3]要么一好一坏，要么两坏，同理，a[5]和a[6]要么一好一坏，要么两好，即a[5]和a[6]至少有一个好。

①如果b[i]一开始是1，那么翻之前为pre+suf，翻了[1,i]之后，总的1的个数为i-(pre+1)+suf-1。②如果b[i]一开始是0，那么翻之前为pre+suf，翻了[1,i]之后，总的1的个数为i-pre+suf。对于n>=2的情况，先问32次询问[2,n]，这样[L,n]对应[2,n]，[1,R]对应[1,n]计[1,i-1]的1的个数为pre，当前无法确定第i位是什么，但是已知[i,n]的个数为suf。那么，如果询问[1,i]的时候，[i+1,n]中01的个数相同，就无法区别是否翻转，

所以，对于所有度为2的点，尝试去用相同的方式染（比如连接父亲的染成颜色1，另一端染成颜色2），类似二分图判定的过程。按照交互机的读入方式，无法区分这两个点，也就无法决定，收到这个读入后该走颜色1还是颜色2。首先，原则肯定是，我们只要能对于深度不同的点能有所区分即可，深度相同的点染一样的无所谓。不妨第一层染1、2，第二层2、3，第三层3、1，以此类推，就可以循环下去了。如果点2的染色方案是1、2，点3的染色方案是2、1的话，颜色为1，为2，...，为k的边的条数各有多少个。

交互题，每次你可以询问一个区间[l,r]的逆序对数，代价是。t(t<=100)组样例，长为n(n<=2000)的序列。感觉有点哈夫曼树贪心的意思，也有点启发式NTT的合并方式。先把n和n-1放两边，n-2放中间，然后递归左右。每次遍历链表，找到位置最接近的两个数询问。于是，想到的最接近3n方次数的构造方法是。的代价内问出最大元素的位置，输出其位置。根据这个尝试去构造对应的hack方法，找到左区间和右区间的极大值的位置，的搞过去了，也就是分治左右区间，把他们按位置增序维护在链表里，

AtCoder Regular Contest 154 D. A + B > C ?（思维题/排序）

题目交互题，首先给定一个n(n<=1e5)，并想好一个数x(1<=x<=n)，你需要在不超过10000次操作中，猜出这个数x，集合S里初始有{1,...,n}共n个数，操作分三种，①A a，询问当前集合中a的倍数有多少个②B a(a>1)，询问当前集合中a的倍数有多少个，并删掉a的倍数，特别地，x不会被删掉③C a，猜出当前的数x的值为a，只能执行一次，程序会被结束思路来源codeforces群里口胡题解sum实时统计当前还有多少数没有被删，

题目n(n<=2e5)个数的数组a[]，ai在[1,1e9]间，数组内的数是非严格单增的，现在需要猜出这个数组，每次询问输入，? l r，代表询问[l,r]的众数，系统会返回这个区间内众数x及其次数f，如存在多个众数，则会返回最小的那个，保证数组内的不同元素数量为k(k<=min(n,25000))，但k未知，你需要不超过4*k次询问，询问出这个数组，最后输出不算次数交互题日常，输出完之后fflush(stdout)思路来源https://blog.csdn.

题目T(T<=10)组样例，每次给定一棵n(2<=n<=1e3)节点的树，并预先选好树上两个不同的点u和v，每次你可以给出一个点集S，以S的大小和S内的点的方式输入，输出会返回一个dis(i,u)+dis(i,v)最小的点i，并返回dis(i,u)+dis(i,v)的值最多11次询问，要求最终猜出最后的不同的两个点u和v思路来源官方题解题解交互，最烦人的地方，就是没办法debug，自己造的样例怎么试怎么过，然而就怎么交怎么wa首先，如果可以询问.

Codeforces Round #648 (Div. 2) G.Secure Password(交互题+数论Sperner定理)

题意交互题，要猜a和b，你输入c和d，记e=a异或c，f=b异或de&gt;f返回1，e==f返回0，e&lt;f返回-1给你最多62次机会，要求猜出a和b思路来源https://blog.csdn.net/weixin_43790474/article/details/84815383傅老师%%%题解（c,d）代表读入了(? c d)询问(now1,n...