整段修改刚开始还求前后两值的差，卡了一下发现直接改就行了。 题意和题解： 线段树板子区间修改区间查询，由于本题查一整段所以无需查询操作 代码： //修改区间为同一个值  #include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N = 1e5 + 10; int T, n, m; struct Node{ int l, r; int sum, add; }tr[N << 2]; void pushup(int u) { tr[u].s...

题意/题解： 给定一个字符串，     1.    1.   1.修改某个字符串中的某个字符，     2.    2.   2.查询字符串某个区间中不同字符的个数。26棵线段树套板子即可。 又是一道直接区修问题，还不太熟悉这类的具体修改，其实还可以加个     l   a   z   y    lazy   lazy标记，不过查询并不多直接做就好了，由于每次修改只涉及两个字符所以只需要修这两棵线段树即可。  #include<bits/stdc++.h> using namespace std; const int N = 5e5 + 10; char s[N]; int n, ...

（这题和之前的某道区间建立正好相反，给整懵了。） 题意： 给定一个长为     8000    8000   8000的区间，每次染色一定长度的区间，最后问你每种颜色的区间有多少段。 题解： 注意必须建     8000    8000   8000的树，然后模拟下递归过程（蒟蒻只会这么推）改下查询操作。  代码： #include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N = 8010; struct Node{ int l, r, c; }...

题面： 年轻的探险家来到了一个印第安部落里。在那里他和酋长的女儿相爱了，于是便向酋长去求亲。酋长要他用10000个金币作为聘礼才答应把女儿嫁给他。探险家拿不出这么多金币，便请求酋长降低要求。酋长说："嗯，如果你能够替我弄到大祭司的皮袄，我可以只要8000金币。如果你能够弄来他的水晶球，那么只要5000金币就行了。“探险家就跑到大祭司那里，向他要求皮袄或水晶球，大祭司要他用金币来换，或者替他弄来其他的东西，他可以降低价格。探险家于是又跑到其他地方，其他人也提出了类似的要求，或者直接用金币换，或者找到其他东西就可以降低价格。不过探险家没必要用多样东西去换一样东西，因为不会得到更低的价格。...

题意： 给两个序列，元素只含     1    1   1和     0    0   0，     a    a   a序列长度为     n    n   n，     b    b   b序列长度为     m    m   m，将     a    a   a看为列矩阵，     b    b   b 看为行矩阵，     c    c   c矩阵为     a   ∗   b    a*b   a∗b得到的矩阵，现在问你可以从中截取多少个面积为     a   r   e   a    area   area的矩阵。 题解： 预处理     a   r   e   a    area...

题意： 给定一个长度为     n    n   n的序列，初始所有元素都是     1    1   1。现在有三种操作：      D  <mtext>   </mtext>  x    D \ x   D x表示将     x    x   x位置的元素由1改成0，     R    R   R表示将最近一次被修改成     0    0   0的元素改成改成     1    1   1，     Q  <mtext>   </mtext>  x    Q \ x   Q x表示求得最长的全     1    1   1序列，其中序列必须...

题意： 一个公司内共     n    n   n个人，给出这     n    n   n个人的上下级关系。一个人下属的下属也是他的下属。当一个人被分配了新的工作时，他的所有下属也将被分配这个新的工作(所有下属停止当前做的工作开始做新的工作)。每个人初始的工作为     −   1    -1   −1，     m    m   m次操作每次要么查询编号为     x    x   x人正在做的工作，要么更新一个人要做的工作(他的所有下属工作也将被更新)。 题解：      d   f   s    dfs   dfs序求出一个人所有的下属，然后线段树区间更新单点查询即可。 忘初始化无限 ...

题意： 给定一个长度为     n    n   n的排列     q    q   q，即     n    n   n个元素值都属于     1   ∼   n    1 \sim n   1∼n，且     n    n   n个元素互不相同。 修改操作：将     q   [   p   o   s   ]    q[pos]   q[pos]加上     1   e   7    1e7   1e7。查询操作：找到与     q   [   1   ∼   r   ]    q[1 \sim r]   q[1∼r]都不相同的且不小于     k    k   k的最小值。 题解： 通...

题解： 二维最长上升子序列输出路径。常规操作先按     w    w   w排序。然后     O   (    n   2    )    O(n^2)   O(n2)暴力即可。 这题没看数据范围直接莽了     O   (   n   l   o   g   n   )    O(nlogn)   O(nlogn)的做法，被卡了三发后逐渐明白错误原因(也可能是我根本就不会这题     O   (   n   l   o   g   n   )    O(nlogn)   O(nlogn)做法)。 显然的是，每个     w    w   w下的     h    h   h在答案中只会出...

题意：      A   l   i   c   e    Alice   Alice有     n    n   n个花瓶，编号从     0   ∼   n    0\sim n   0∼n。每个花瓶可以插一朵花，每当他收到     F    F   F朵花时，她将随机选择一个编号为     A    A   A的花瓶，从这个花瓶开始往后到第     n   −   1    n-1   n−1个花瓶，每当花瓶没有花时，可以将一朵花插在这个花瓶上。（当     A   ∼   n   −   1    A\sim n-1   A∼n−1的花瓶都插满花了但是F朵花没有插完，也会停止）。 操作...

题意： 给定一个长度为     n    n   n的序列     B    B   B，对于任意的整数，当     ∣   i   −   j   ∣    |i-j|   ∣i−j∣属于     B    B   B时，点     i    i   i和点     j    j   j之间会连一条边，问至少删除     B    B   B中多少元素可以使得所有整数形成的图是一个二分图 题解： 二分图的性质：一个图为二分图当且仅当图中不存在奇数环。 那么借助这个性质，我们先考虑将当前符合条件的整数，即两个整数差的绝对值在     B    B   B中存在时，将其连上一条边。那么对于存在于...

题意： 给定一个长度为     n    n   n的坐标序列     a    a   a，以及一个坐标      M   0     M_0   M0​。      M   i     M_i   Mi​和      M    i   −   1      M_{i-1}   Mi−1​以      a    {   (   i   −   1   )   m   o   d  <mtext>   </mtext>  n   }      a_{\{(i-1)mod\ n\}}   a{(i−1)mod n}​对称，求      M   j     M_j   Mj...

自从换了新电脑后，编译的时候就从来没有快过，就算编译很快，链接的时候也得等~ 别人题都已经交上去了，我还没从debug后重新编译的噩梦中逃脱出来。 直到我发现了后台的qq电脑管家一直在。。 建议把所有的第三方杀毒、管家之类的所有软件全部关掉，通通关掉。

题解： 当子串长为     1    1   1或者串中字符种类为     1    1   1，显然构造不出。 排除以上情况后，显然无论怎么分割子串，首尾字符是不可能划分到一起的。 思考极端情况时，划分为     s   [   l   ]    s[l]   s[l]和     s   [   l   +   1   ∼   r   ]    s[l+1\sim r]   s[l+1∼r]或者     s   [   l   ∼   r   −   1   ]    s[l\sim r-1]   s[l∼r−1]和     s   [   r   ]    s[r]   s[r]， 故问题...