a：
这道题目还是很简单的，做过很多遍了，类似于切割木板的问题。
把所有的数放在一个优先队列里，弹出两个最大的，然后合并，把结果放进去。依次进行。
#include #include#include#include#include#include#include#includeusing namespace std;#define ll __int64#define inf 1000000000ll a[330000];priority_queueque;int main(){ int n; while(~scanf(%d,&n)) { ll sum=0; while(!que.empty())que.pop(); for(int i=1;ib:树形dp
dp[i][0]:以i节点为根的子树对上面的贡献为0时的情况数
dp[i][1]:以i节点为根的子树对上面的贡献为1时的情况数
如果i节点为0
很明显对于dp[i][1]:
枚举哪颗子树对i贡献了1，假如a,b,c为i的子树，则
dp[i][1]=dp[a][1]*dp[b][0]*dp[c][0]+dp[a][0]*dp[b][1]*dp[c][0]+dp[a][0]*dp[b][0]*dp[c][1];
对于dp[i][0]:
1，如果所有的子树都没有对i贡献
dp[i][0]+=dp[a][0]*dp[b][0]*dp[c][0];
2,存在一个子树对i贡献了1，但是i节点上方的边被切掉
dp[i][0]+=dp[i][1];
如果i节点为1
dp[i][0]=dp[i][1]=dp[a][0]*dp[b][0]*dp[c][0];
#include#include#include#include#include#include#include#includeusing namespace std;#define maxn 110000#define ll __int64#define mod 1000000007vectorold[maxn];vectornow[maxn];int vis[maxn];void change(int x){ int i; vis[x]=1; for(i=0; i>=1; } return ret;}ll dos(ll x,ll y,ll z){ x=x*z; x=x%mod; x=x*q_mod(y,mod-2,mod); x=x%mod; return x;}void dfs(int x){ int leap=0; ll sum=1; for(int i=0; i
c:
很明显，如果翻转大于一半，相当于先旋转，然后翻转剩下的。
那么我们最多会翻转2*n个数字。然后就暴力枚举当前的状态。
然后用线段树储存每个节点有多少长度，然后询问的时候区间求和。
#include#include#include#include#include#include#include#includeusing namespace std;#define maxn 110000#define ll __int64#define mod 1000000007#define mem(a,b) (memset(a),b,sizeof(a))#define lmin 1#define rmax n#define lson l,(l+r)/2,rtr||llr||rr=r)return sum[rt]; return query(ll,rr,lson)+query(ll,rr,rson);}int leap,st,ed,n;void chu(int p){ if(leap==0) { st=st+p; ed=ed; for(int i=p; i>=1; i--) { have[st+i-1]=have[st+i-1]+have[st-i]; updata(st+i-1,have[st+i-1],root); } } else { ed=ed-p; st=st; for(int i=p; i>=1; i--) { have[ed-i+1]=have[ed-i+1]+have[ed+i]; updata(ed-i+1,have[ed-i+1],root); } }}int main(){ int q; while(~scanf(%d%d,&n,&q)) { creat(root); for(int i=1; ied||bed)b=ed; if(a